给定一个由 0 和 1 组成的排序数组，在 C++ 中找到数组的转换点

2023-06-21 10:20:03 82

给定一个只包含0和1的排序数字数组，找到转换点。转换点是数组中出现的第一个“1”的索引。例如，

输入1-

N = 6
arr[ ] = {0,0,0,0,1,1}

输出-

说明-由于在包含0和1的给定数组中，我们可以看到索引“4”处的元素具有数字“1”。

输入2-

N = 5
arr[ ] = {0,0,1,1,1}

输出-

说明-在给定的包含0和1的数组中，我们可以看到索引“2”处的元素具有数字“1”。因此，我们将返回2。

解决这个问题的方法

在给定的整数数组中，我们必须找到第一个1的索引。为了解决这个特殊问题，我们可以使用二进制搜索方法来解决它，以找到第一个'1'的索引。

输入一个包含N个二进制数的数组

现在，函数transitionPoint(int*arr,intn)将数组作为输入及其大小，并返回数组中出现的第一个“1”的索引。

取两个指针低，高，初始化为“0”和“1”。

现在我们将找到数组的中点并检查它是否为“1”。

如果数组的中间是“1”，那么我们将返回它的索引，否则我们将继续检查。

增加低指针并再次检查“1”。

重复这些步骤，直到我们没有得到“1”。

示例

#include 
using 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'。

给定一个由 0 和 1 组成的排序数组，在​​ C++ 中找到数组的转换点

解决这个问题的方法

示例

热门推荐

随机推荐

给定一个由 0 和 1 组成的排序数组，在 C++ 中找到数组的转换点