C++에서 정렬된 무한 숫자 배열에서 요소의 위치 찾기

이 문제에서는 무한히 정렬된 숫자로 구성된 배열이 제공됩니다. 우리의 임무는 정렬된 무한 숫자 배열에서 요소의 위치를 ​​찾는 것입니다.

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

입력

arr[] = {2, 4, 6, 8, 9, 12, 14,17, ….}, ele = 9

출력

4

설명

솔루션 접근 방식

정렬된 배열에서 요소를 효율적으로 검색하기 위해 이진 검색 방법을 사용합니다. 여기서 단일 종점을 알 수 없으므로 알고리즘을 약간 수정합니다.

시작 포인터를 첫 번째 위치로 고정한 다음 끝 포인터를 두 번째 위치로 가져옵니다. 그런 다음 끝 포인터의 값을 확인하고 값이 키보다 작으면 두 배로 늘리고 끝 포인터의 마지막 위치로 시작 포인터를 업데이트합니다.

마지막 위치 값이 찾을 요소보다 크면 이진 검색을 사용하여 이 하위 배열에서 검색합니다.

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

예시

#include<iostream>
using namespace std;
int binarySearch(int arr[], int start, int end, int ele) {
   if (end >= start) {
      int mid = start + (end - start)/2;
      if (arr[mid] == ele)
         return mid;
      if (arr[mid] > ele)
         return binarySearch(arr, start, mid-1, ele);
      return binarySearch(arr, mid+1, end, ele);
   }
   return -1;
}
int findPos(int arr[], int value) {
   int start = 0, end = 1;
   while (arr[end] < value) {
      start = end;
      end = 2*end;
   }
   return binarySearch(arr, start, end, value);
}
int main(){
   int arr[] = {1, 2, 4, 6, 8, 9, 12, 14, 17, 21, 45};
   int index = findPos(arr, 9);
   if (index == -1)
      cout<<"Element not found!";
   else
      cout<<"Element found! index = "<<index;
   return 0;
}

출력

Element found! index = 5