在 C++ 中查找无限排序的 0 和 1 数组中第一个 1 的索引

在这个问题中，我们得到一个无限数组 bin[]，它包含按排序顺序排列的布尔值（只有 0 和 1）。我们的任务是查找无限排序的 0 和 1 数组中第一个 1 的索引。

这里，我们有一个无限数组，它保证数组中存在 1。

让我们举个例子来理解这个问题，

Input : bin[] = {0, 0, 0, 1, 1, ....}
Output : 3

说明 -

First 1 of the binary array is encountered at index 3.

解决方案方法

为了解决这个问题，我们基本上需要找到数组中第一个 1 的索引。为此，我们可以使用搜索技术。

一种方法可以使用线性搜索，我们将使用无限循环遍历数组。并返回数组中第一个 1 的索引，否则打印 -1。

示例

程序说明我们解决方案的工作原理

Open Compiler
#include <iostream>
using namespace std;
double find1stOneInfiniteArray(int bin[]) {
   int i = 0;
   while(1){
      if (bin[i] == 1)
         return i;
      i++;
   }
   return -1;
}
int main() {
   int bin[] = { 0, 0, 0, 1, 1, 1 };
   cout<<"The index of 1st occurrence of 1 in infinite array is "<<find1stOneInfiniteArray(bin);
   return 0;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

The index of 1st occurrence of 1 in infinite array is 3

另一种可以使用的搜索技术是二分查找，因为数组已排序。

我们只需要更新算法，因为没有上限，我们将通过将 high 的值从索引值 1 加倍到第一个 1 出现的索引来找到它。

使用这些边界，我们可以使用二分查找找到索引。

示例

程序说明我们解决方案的工作原理

Open Compiler
#include <iostream>
using namespace std;
double find1stOneInfiniteArray(int bin[], int low, int high) {
   int mid;
   while (low <= high) {
      mid = (low + high) / 2;
      if (bin[mid] == 1 && (mid == 0 || bin[mid - 1] == 0))
         return mid;
      else if (bin[mid] == 1)
         high = mid - 1;
      else
         low = mid + 1;
   }
   return -1;
}
int main() {
   int bin[] = { 0, 0, 0, 1, 1, 1, 1 };
   int low = 0;
   int high = 1;
   while(bin[high] != 1){
      low = high;
      high *= 2;
   }
   cout<<"The index of 1st occurrence of 1 in infinite array is " <<find1stOneInfiniteArray(bin,low, high);
   return 0;
}

输出

The index of 1st occurrence of 1 in infinite array is 3

更新于： 2022-01-28

477 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告