算法基础：二分搜索 (Binary Search)

二分搜索简介

二分搜索是一种在 有序数组 中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是目标值，则搜索过程结束；如果目标值大于或小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。

算法步骤

1. 设定左边界 left 和右边界 right。
2. 当 left <= right 时，循环执行： a. 计算中间位置 mid = left + (right - left) / 2。 b. 如果 array[mid] 等于目标值，则返回 mid。 c. 如果 array[mid] 小于目标值，则目标值在右半部分，更新 left = mid + 1。 d. 如果 array[mid] 大于目标值，则目标值在左半部分，更新 right = mid - 1。
3. 如果循环结束仍未找到，则返回 -1。

代码实现 (C++)

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid; // 找到目标
        } else if (arr[mid] < target) {
            left = mid + 1; // 目标在右侧
        } else {
            right = mid - 1; // 目标在左侧
        }
    }

    return -1; // 未找到
}

复杂度分析

• 时间复杂度: O(log n)，因为每次操作都将搜索空间减半。
• 空间复杂度: O(1)，因为它只需要常数个额外变量。

二分搜索是计算机科学中非常基础且重要的算法，是许多更复杂算法和数据结构的基础。