Tìm chỉ số của 1 đầu tiên trong một mảng được sắp xếp vô hạn gồm 0 và 1 trong C ++

Trong bài toán này, chúng ta được cung cấp một dãy vô hạn bin [] bao gồm các giá trị boolean (chỉ có 0 và 1) theo thứ tự được sắp xếp. Nhiệm vụ của chúng tôi là tìm chỉ mục của 1 đầu tiên trong một mảng được sắp xếp vô hạn của 0 và 1 .

Ở đây, chúng ta có một mảng vô hạn đảm bảo rằng tồn tại 1 trong mảng.

Hãy lấy một ví dụ để hiểu vấn đề,

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

Giải thích -

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

Phương pháp tiếp cận giải pháp

Để giải quyết vấn đề, về cơ bản chúng ta cần tìm chỉ số của 1 1 trong mảng. Để làm được điều đó, chúng tôi có thể sử dụng kỹ thuật tìm kiếm.

Một cách tiếp cận có thể là sử dụng tìm kiếm tuyến tính, chúng tôi sẽ duyệt qua mảng bằng cách sử dụng một vòng lặp vô hạn. Và trả về chỉ số của 1 đầu tiên trong mảng, nếu không thì in ra -1.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

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

Một kỹ thuật tìm kiếm khác có thể được sử dụng là tìm kiếm nhị phân vì mảng được sắp xếp.

Chỉ cần chúng ta cập nhật thuật toán vì không có giới hạn trên, chúng ta sẽ tìm thấy nó bằng cách nhân đôi giá trị cao bắt đầu từ giá trị chỉ mục 1 đến chỉ số xuất hiện của 1 đầu tiên.

Sử dụng các giới hạn này, chúng tôi có thể tìm chỉ mục bằng cách sử dụng tìm kiếm nhị phân.

Ví dụ

Chương trình minh họa hoạt động của giải pháp của chúng tôi

#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;
}

Đầu ra

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