이 문제에서는 부울 값(0과 1만)으로 구성된 무한 배열 bin[]이 정렬된 순서로 주어집니다. 우리의 임무는 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을 인쇄합니다.
예시
솔루션 작동을 설명하는 프로그램
#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; }
출력
The index of 1st occurrence of 1 in infinite array is 3
또 다른 검색 기술 사용할 수 있는 것은 배열이 정렬될 때 이진 검색입니다.
상한이 없기 때문에 알고리즘을 업데이트하기만 하면 됩니다. 인덱스 값 1에서 시작하여 처음 1의 발생 인덱스까지 high 값을 두 배로 늘려서 찾을 것입니다.
이 경계를 사용하여 이진 검색을 사용하여 색인을 찾을 수 있습니다.
예시
솔루션 작동을 설명하는 프로그램
#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