C++で無限数のソートされた配列内の要素の位置を検索します

この問題では、無限にソートされた数で構成される配列が与えられます。私たちのタスクは、無限にソートされた数の配列内の要素の位置を見つけることです。

問題を理解するために例を見てみましょう

入力

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

出力

4

説明

ソリューションアプローチ

ソートされた配列から要素を効率的に検索するために、バイナリ検索方法を使用します。ここでは、単一のエンドポイントが不明であるため、アルゴリズムを少し変更します。

開始ポインターを最初の位置に固定し、次に終了ポインターを2番目の位置に固定します。この後、エンドポインターの値を確認し、値がキーよりも小さい場合は値を2倍にしてインクリメントし、開始ポインターをエンドポインターの最後の位置で更新します。

最後の位置の値が検出される要素よりも大きい場合、バイナリ検索を使用してこのサブ配列を検索します。

ソリューションの動作を説明するプログラム

例

#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