实现一个二分搜索算法，搜索指定元素在已排序数组中的位置。（递归或者非递归实现）
简介：实现一个二分搜索算法，搜索指定元素在已排序数组中的位置。（递归或者非递归实现）
算法思路
算法思路
二分查找是一种在有序数组中查找特定元素的搜索算法。该算法对数组进行比较次数的上限是 O(log n)。核心思想是通过每次将查找区间缩小一半来逐步接近查找目标。因为每次查找后查找区间都缩小了一半，所以时间复杂度是对数级别。
具体实现如下：
- 选择左右两端点取中间值，然后与目标值相比较
- 如果当前中间值大于目标值，则说明目标值只可能在mid左侧，所以再次在[l, mid-1]区间进行查找
- 如果当前中间值小于目标值，则说明目标值只可能在mid右侧，所以再次在[mid+1, r]区间进行查找
- 重复执行步骤1~3，直到找到目标值或确定不存在目标值
下面是C++代码实现，每行注释详细解释其作用：
#include <iostream> using namespace std; int binarySearch(int arr[], int l, int r, int x) { // 当前查找区间为 [left, right] if (r >= l) { // 当还有剩余未查找的元素时循环 int mid = l + (r - l) / 2; // 取中间值 if (arr[mid] == x) return mid; // 如果中间值等于目标值，则直接返回 if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // 如果中间值大于目标值，则在左边的区间中查找 return binarySearch(arr, mid + 1, r, x); // 否则在右边的区间中查找 } return -1; // 如果数组中不存在目标元素，则返回-1 } int main() { int arr[] = {1, 3, 5, 7, 9}; // 已排序数组a int n = sizeof(arr) / sizeof(arr[0]); // 数组长度为n int x = 5; // 要查找的元素x int result = binarySearch(arr, 0, n - 1, x); // 调用二分搜索函数 cout << "The index of " << x << " in array is: " << result << endl; // 输出结果 return 0; }
需要注意的是，在实现中我们使用递归方式进行查找。每次将当前查找区间中点与目标值进行比较，如果相等，则表示已经找到目标元素；如果中间值大于目标元素，则说明目标元素只可能在mid左侧，所以再次在[l, mid-1]区间进行查找；否则说明目标元素只可能在mid右侧，所以再次在[mid+1, r]区间进行查找。重复执行这个过程，直到找到或确定不存在目标元素。
同时，递归方式的实现还需要注意满足递归退出条件。当当前查找区间[l, r]变成[low, high]时，如果high < low，则说明不存在目标元素，返回-1即可。
- Java版本
class Solution { public int binarySearch(int[] arr, int l, int r, int x) { if (r >= l) { // 当还有剩余未查找的元素时循环 int mid = l + (r - l) / 2; // 取中间值 if (arr[mid] == x) return mid; // 如果中间值等于目标值，则直接返回 if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // 如果中间值大于目标值，则在左边的区间中查找 return binarySearch(arr, mid + 1, r, x); // 否则在右边的区间中查找 } return -1; // 如果数组中不存在目标元素，则返回-1 } public static void main(String[] args) { Solution sol = new Solution(); int[] arr = {1, 3, 5, 7, 9}; // 已排序数组a int n = arr.length; // 数组长度为n int x = 5; // 需要查找的目标值 int result = sol.binarySearch(arr, 0, n - 1, x); // 调用二分搜索函数 System.out.println("The index of " + x + " in array is: " + result); // 输出结果 } }
同样地，在Java中我们也使用递归方式进行查找。每次将当前查找区间中点与目标值进行比较，如果相等，则表示已经找到目标元素；如果中间值大于目标元素，则说明目标元素只可能在mid左侧，所以再次在[l, mid-1]区间进行查找；否则说明目标元素只可能在mid右侧，所以再次在[mid+1, r]区间进行查找。重复执行这个过程，直到找到或确定不存在目标元素。
同时，递归方式的实现还需要注意满足递归退出条件。当当前查找区间[l, r]变成[low, high]时，如果high < low，则说明不存在目标元素，返回-1即可。
