C++에서 0과 1의 정렬된 배열에서 처음 1의 인덱스 찾기

이 문제에서는 부울 값(0과 1만)으로 구성된 배열 bin[]이 정렬된 순서로 제공됩니다. 우리의 임무는 0과 1의 정렬된 배열에서 처음 1의 인덱스를 찾는 것입니다. .

문제를 이해하기 위해 예를 들어 보겠습니다.

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

설명 -

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

솔루션 접근 방식

문제를 해결하려면 기본적으로 배열에서 1번째 1의 인덱스를 찾아야 합니다. 이를 위해 검색 기술을 사용할 수 있습니다.

한 가지 접근 방식은 선형 검색을 사용하는 것입니다. 인덱스 0에서 배열 끝까지 배열을 탐색합니다. 그리고 배열의 처음 1의 인덱스를 반환하고, 그렇지 않으면 -1을 인쇄합니다.

예시

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
double find1stOneInArray(int bin[], int n) {
   for (int i = 0; i < n; i++)
      if (bin[i] == 1)
         return i;
      return -1;
}
int main() {
   int bin[] = { 0, 0, 0, 1, 1, 1 };
   int n = sizeof(bin) / sizeof(bin[0]);
      cout<<"The index of 1st occurrence of 1 in array is "<<find1stOneInArray(bin,n);
      return 0;
}

출력

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

또 다른 검색 기술 사용할 수 있는 것은 배열이 정렬될 때 이진 검색입니다.

예시

솔루션 작동을 설명하는 프로그램

#include <iostream>
using namespace std;
double find1stOneInArray(int bin[], int n) {
   int low = 0;
   int high = (n - 1);
   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 n = sizeof(bin) / sizeof(bin[0]);
      cout<<"The index of 1st occurrence of 1 in array is "<<find1stOneInArray(bin,n);
   return 0;
}

출력

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