给定一个由 0 和 1 组成的排序数组,在 C++ 中找到数组的转换点
给定一个只包含0和1的排序数字数组,找到转换点。转换点是数组中出现的第一个“1”的索引。例如,
输入1-
N = 6 arr[ ] = {0,0,0,0,1,1}
输出-
4
说明-由于在包含0和1的给定数组中,我们可以看到索引“4”处的元素具有数字“1”。
输入2-
N = 5 arr[ ] = {0,0,1,1,1}
输出-
2
说明-在给定的包含0和1的数组中,我们可以看到索引“2”处的元素具有数字“1”。因此,我们将返回2。
解决这个问题的方法
在给定的整数数组中,我们必须找到第一个1的索引。为了解决这个特殊问题,我们可以使用二进制搜索方法来解决它,以找到第一个'1'的索引。
输入一个包含N个二进制数的数组
现在,函数transitionPoint(int*arr,intn)将数组作为输入及其大小,并返回数组中出现的第一个“1”的索引。
取两个指针低,高,初始化为“0”和“1”。
现在我们将找到数组的中点并检查它是否为“1”。
如果数组的中间是“1”,那么我们将返回它的索引,否则我们将继续检查。
增加低指针并再次检查“1”。
重复这些步骤,直到我们没有得到“1”。
示例
#includeusing namespace std; int transitionPoint(int *arr, int n){ int low=0; int high= n-1; while(low<=high){ int mid = (low+high)/2; if(arr[mid]==0) low= mid+1; else if(arr[mid]==1){ if(mid==0 || (mid>0 && arr[mid-1]==0)) return mid; high= mid-1; } } return -1; } int main(){ int n= 6; int arr[n]= {0,0,0,1,1,1}; int ans= transitionPoint(arr,n); if(ans>=0){ cout<<"过渡点是:"< 输出结果 运行上面的代码将生成输出,
过渡点是: 3给定的数组{0,0,0,1,1,1}在索引'3'处有元素'1',因此我们得到输出为'3'。