实现一个二分搜索算法，搜索指定元素在已排序数组中的位置。（递归或者非递归实现）

简介：实现一个二分搜索算法，搜索指定元素在已排序数组中的位置。（递归或者非递归实现）

算法思路

算法思路

二分查找是一种在有序数组中查找特定元素的搜索算法。该算法对数组进行比较次数的上限是 O(log n)。核心思想是通过每次将查找区间缩小一半来逐步接近查找目标。因为每次查找后查找区间都缩小了一半，所以时间复杂度是对数级别。

具体实现如下：

1. 选择左右两端点取中间值，然后与目标值相比较
2. 如果当前中间值大于目标值，则说明目标值只可能在mid左侧，所以再次在[l, mid-1]区间进行查找
3. 如果当前中间值小于目标值，则说明目标值只可能在mid右侧，所以再次在[mid+1, r]区间进行查找
4. 重复执行步骤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即可。