C ++中的二进制搜索

二进制搜索是一种通过重复将数组减半并进行一半搜索来在排序后的数组中查找所需元素的方法。

该方法是从整个数组开始的。然后将其减半。如果所需的数据值大于数组中间的元素，则考虑数组的上半部分。否则，将考虑下半部分。连续进行此操作，直到获得所需的数据值或剩余的数组为空为止。

下面给出了一个演示用C ++进行二进制搜索的程序。

示例

#include<iostream>
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 = 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;
}

输出结果

33 is present at index 7 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()调用以找到编号的索引。如果by返回的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;
}