博客详情 - oirush

admin 的博客
二分查找 (Binary Search)
admin SU @ 2026-6-7 19:55:09

算法概述

二分查找（Binary Search），也称折半查找，是一种在有序数组中查找目标值的高效算法。其基本思想是：每次将搜索范围缩小一半，直到找到目标值或搜索范围为空。

二分查找是计算机科学中最基础也最重要的算法之一，其思想渗透到各种算法和数据结构中（如二分搜索树、二分答案等），是所有程序员必须熟练掌握的核心算法。

核心思想

在有序数组中，每次选取当前搜索区间的中间元素与目标值比较：

若中间元素等于目标值 → 找到，返回下标。
若中间元素大于目标值 → 目标值只可能在左半部分，收缩右边界。
若中间元素小于目标值 → 目标值只可能在右半部分，收缩左边界。

每次比较后，搜索范围减半，因此时间复杂度为 O(log n)。

核心前提：数组必须是有序的（递增或递减均可，通常指递增）。如果数组无序，需要先排序，但排序本身通常需要 O(n log n) 的时间。

算法步骤 / 伪代码

迭代版本（最常用）

function binarySearch(arr, target):
    left = 0
    right = arr.length - 1
    while left <= right:
        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                              // 未找到

递归版本

function binarySearchRecursive(arr, left, right, target):
    if left > right:
        return -1                          // 未找到
    mid = left + (right - left) / 2
    if arr[mid] == target:
        return mid
    else if arr[mid] < target:
        return binarySearchRecursive(arr, mid + 1, right, target)
    else:
        return binarySearchRecursive(arr, left, mid - 1, target)

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

// ============ 1. 迭代版本（推荐） ============
int binarySearch(const vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 防溢出写法（比 (left+right)/2 更安全）

        if (arr[mid] == target) {
            return mid;                      // 找到目标，返回下标
        } else if (arr[mid] < target) {
            left = mid + 1;                  // 目标在右半部分
        } else {
            right = mid - 1;                 // 目标在左半部分
        }
    }
    return -1;                               // 未找到
}

// ============ 2. 递归版本 ============
int binarySearchRecursive(const vector<int>& arr, int left, int right, int target) {
    if (left > right) {
        return -1;                           // 未找到
    }

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

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, mid + 1, right, target);
    } else {
        return binarySearchRecursive(arr, left, mid - 1, target);
    }
}

// ============ 3. 查找第一个等于 target 的位置（下界） ============
int lowerBound(const vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;  // 返回第一个 >= target 的位置
}

// ============ 4. 查找最后一个等于 target 的位置 ============
int upperBound(const vector<int>& arr, int target) {
    int left = 0, right = arr.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left - 1;  // 返回最后一个 <= target 的位置
}

// ============ 5. LeetCode 33：搜索旋转排序数组 ============
int searchRotated(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;

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

        if (nums[mid] == target) return mid;

        // 判断哪一半是有序的
        if (nums[left] <= nums[mid]) {
            // 左半部分有序
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;   // target 在左半部分
            } else {
                left = mid + 1;    // target 在右半部分
            }
        } else {
            // 右半部分有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;    // target 在右半部分
            } else {
                right = mid - 1;   // target 在左半部分
            }
        }
    }
    return -1;
}

// ============ 主函数 ============
int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};

    cout << "有序数组: ";
    for (int x : arr) cout << x << " ";
    cout << endl << endl;

    // ---- 测试基本二分查找 ----
    cout << "=== 基本二分查找 ===" << endl;
    int targets[] = {7, 10, 1, 19, 0};
    for (int t : targets) {
        int idx = binarySearch(arr, t);
        cout << "查找 " << t << ": ";
        if (idx != -1) cout << "找到，下标 = " << idx << endl;
        else           cout << "未找到" << endl;
    }

    // ---- 测试递归版本 ----
    cout << "\n=== 递归版本 ===" << endl;
    cout << "查找 11: 下标 = "
         << binarySearchRecursive(arr, 0, arr.size() - 1, 11) << endl;

    // ---- 测试 lower_bound / upper_bound ----
    vector<int> arr2 = {1, 2, 2, 2, 3, 4, 5};
    cout << "\n=== lower_bound / upper_bound ===" << endl;
    cout << "数组: ";
    for (int x : arr2) cout << x << " ";
    cout << endl;
    cout << "第一个 2 的位置 (lowerBound): " << lowerBound(arr2, 2) << endl;
    cout << "最后一个 2 的位置 (upperBound): " << upperBound(arr2, 2) << endl;

    // ---- 测试搜索旋转排序数组（LeetCode 33）----
    cout << "\n=== LeetCode 33：搜索旋转排序数组 ===" << endl;
    vector<int> rotated = {4, 5, 6, 7, 0, 1, 2};
    cout << "旋转数组: ";
    for (int x : rotated) cout << x << " ";
    cout << endl;

    int testVals[] = {0, 3, 6, 4};
    for (int t : testVals) {
        int idx = searchRotated(rotated, t);
        cout << "查找 " << t << ": ";
        if (idx != -1) cout << "找到，下标 = " << idx << endl;
        else           cout << "未找到" << endl;
    }

    return 0;
}

复杂度分析

指标	值
时间	O(log n)
空间	O(1)（迭代）/ O(log n)（递归）
前提	数组必须有序

时间复杂度：每次比较将搜索范围减半，最多需要 ⌈log₂(n+1)⌉ 次比较，即 O(log n)。即使对十亿级别的数据，也只需要约 30 次比较。
空间复杂度：
- 迭代版本：O(1)，只使用常数个变量。
- 递归版本：O(log n)，递归调用栈深度为 log n。
与线性查找对比：顺序查找需要 O(n) 的时间，二分查找在百万级数据中只需约 20 次比较，效率提升巨大。

应用场景

有序序列查找：最直接的应用——在排序数组、有序集合中查找特定元素。
二分答案：当问题满足"单调性"时，可以二分枚举可能的答案。例如："最小的满足条件的值"、"最大的不满足条件的值"。这是二分思想最重要的扩展应用。
查找边界：使用 lower_bound / upper_bound 查找有序数组中某个值的起始位置和结束位置（C++ STL 中的 std::lower_bound 和 std::upper_bound）。
搜索旋转数组：在发生了旋转的有序数组中查找目标值（如 LeetCode 33）。
求平方根/指数运算：使用二分查找逼近无理数的值（如求 √2、实现 pow 函数等）。
矩阵搜索：在行列均有序的二维矩阵中使用二分查找。

经典例题

LeetCode 33 — 搜索旋转排序数组

题目描述：整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在某个未知下标 k 上进行了旋转（例如 [0,1,2,4,5,6,7] 在下标 3 处旋转后变为 [4,5,6,7,0,1,2]）。给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。要求 O(log n) 时间。

示例：

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

二分查找解法思路：

虽然整个数组不是完全有序的，但每次取中点后，至少有一半是有序的。
判断哪一半有序（通过比较 nums[left] 和 nums[mid]）。
判断 target 是否在有序的那一半中：
- 如果在，则在有序的一半中继续二分查找。
- 如果不在，则在另一半（旋转的一半）中继续查找。
每次仍然排除一半元素，保持 O(log n) 的时间复杂度。

（完整 C++ 代码已包含在上方的代码实现中）

二分查找 (Binary Search)

算法概述

核心思想

算法步骤 / 伪代码

迭代版本（最常用）

递归版本

C++ 代码实现

复杂度分析

应用场景

经典例题

LeetCode 33 — 搜索旋转排序数组

状态

开发

支持

关于

二分查找 (Binary Search)

算法概述

核心思想

算法步骤 / 伪代码

迭代版本（最常用）

递归版本

C++ 代码实现

复杂度分析

应用场景

经典例题

LeetCode 33 — 搜索旋转排序数组

状态

开发

支持

关于

还没有账户？

登录