二分查找算法讲解及其C++代码实现

二分查找算法是一种常用的查找算法，也被称为折半查找。它可以在有序的数组或列表中快速查找需要的元素。
算法描述：

• 首先确定数组的中间位置mid=(left+right)/2；
  
• 然后将要查找的值key与中间位置的值进行比较；
  
• 如果key等于中间位置的值，则查找成功，返回mid；
  
• 如果key小于中间位置的值，则在左半部分继续查找；
  
• 如果key大于中间位置的值，则在右半部分继续查找；
  
• 重复以上步骤，直到查找到key或者left>right时，查找结束。
  

C++代码实现：

1. int binarySearch(int arr[], int n, int key)
2. {
3.     int left = 0;
4.     int right = n - 1;
5.     while (left <= right)
6.     {
7.         int mid = (left + right) / 2;
8.         if (arr[mid] == key)
9.             return mid;
10.         else if (arr[mid] > key)
11.             right = mid - 1;
12.         else if (arr[mid] < key)
13.             left = mid + 1;
14.     }
15.     return -1; // 查找失败，返回-1
16. }

复制代码

该函数接收三个参数，分别是：

• arr：有序数组指针；
  
• n：数组长度；
  
• key：要查找的值。
  

如果查找成功，函数将返回该元素在数组中的下标；否则，返回-1表示查找失败。
注意：使用二分查找算法前，必须先对数组进行排序。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！