C++での二分探索

二分探索は、配列を半分にして半分ずつ検索することにより、並べ替えられた配列から必要な要素を見つける方法です。

このメソッドは、アレイ全体から開始することによって実行されます。それからそれは半分になります。必要なデータ値が配列の中央にある要素よりも大きい場合は、配列の上半分が考慮されます。それ以外の場合は、下半分が考慮されます。これは、必要なデータ値が取得されるか、残りの配列が空になるまで継続的に実行されます。

C++での二分探索を示すプログラムを以下に示します。

例

#include
using namespace std;
int binarySearch(int arr[], int p, int r, int num) {
   if (p <= r) {
      int mid = (p + r)/2;
      if (arr[mid] == num)
         return mid ;
      if (arr[mid] > num)
         return binarySearch(arr, p, mid-1, num);
      if (arr[mid] < num)
         return binarySearch(arr, mid+1, r, num);
   }
   return -1;
}
int main(void) {
   int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int num;
   cout << "Enter the number to search: \n";
   cin >> num;
   int index = binarySearch (arr, 0, n-1, num);
   if(index == -1){
      cout<< num <<" is not present in the array";
   }else{
      cout<< num <<" is present at index "<< index <<" in the array";
   }
   return 0;
}

出力

Enter the numberto search
20
20 is present at index 5 in the array

上記のプログラムでは、binarySearch（）は、バイナリ検索を使用して配列内の必要な要素を見つけるために使用される再帰関数です。この関数は、配列、その下限と上限、およびパラメーターとして検出される数値を受け取ります。これを以下に示します。

int binarySearch(int arr[], int p, int r, int num)

次に、配列の中点が計算されます。中点の値がnumに等しい場合、それが返されます。値がnumより大きい場合、配列は下限pと上限mid-1を使用して再帰的に呼び出します。値がnum未満の場合、配列は下限のmid+1と上限のrを使用して再帰的に呼び出します。これは、次のコードスニペットで確認できます。

int binarySearch(int arr[], int p, int r, int num) {
   if (p <= r) {
      int mid = (p + r)/2;
      if (arr[mid] == num)
         return mid ;
      if (arr[mid] > num)
         return binarySearch(arr, p, mid-1, num);
      if (arr[mid] < num)
         return binarySearch(arr, mid+1, r, num);
   }
   return -1;
}

main（）関数では、配列arr[]が定義されています。配列のサイズが計算され、検出される数が指定されます。次に、binarySearch（）が呼び出され、番号のインデックスが検索されます。 binarySearch（）によって返される値が-1の場合、その数値は配列に含まれていません。それ以外の場合は、インデックス値が返されます。これを以下に示します。

int main(void) {
   int arr[] = {1, 3, 7, 15, 18, 20, 25, 33, 36, 40};
   int n = sizeof(arr)/ sizeof(arr[0]);
   int num = 33;
   int index = binarySearch (arr, 0, n-1, num);
   if(index == -1)
      cout<< num <<" is not present in the array";
   else
      cout<< num <<" is present at index "<< index <<" in the array";
   return 0;
}