二分查找（算法）

用户11445909

发布于 2025-01-13 20:44:58

9400

代码可运行

文章被收录于专栏：猫咪-9527猫咪-9527

运行总次数：0

代码可运行

1. 普通二分查找

使用场景

在 有序数组 中查找某个期望的值（target）。

算法流程

定义两个指针 left 和 right，分别指向数组的左右边界。
进入循环，条件为 left <= right。
在每次循环中：
- 计算中间点：mid = left + (right - left) / 2（防止整数溢出）。
- 如果 arr[mid] == target，返回 mid。
- 如果 arr[mid] > target，说明目标值在左半部分，更新 right = mid - 1。
- 如果 arr[mid] < target，说明目标值在右半部分，更新 left = mid + 1。
如果循环结束仍未找到目标值，返回 -1。

实现代码

int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1; // 初始化左右指针
    while (left <= right) { // 循环条件
        int mid = left + (right - left) / 2; // 计算中间点，避免溢出
        if (arr[mid] == target) {
            return mid; // 找到目标值
        } else if (arr[mid] > target) {
            right = mid - 1; // 在左半部分查找
        } else {
            left = mid + 1; // 在右半部分查找
        }
    }
    return -1; // 未找到目标值
}

2. 二段性二分查找

使用场景

在多段有序数组（如 旋转数组）或某些条件满足的数组中，找到目标值的区间范围 [begin, end]。

算法流程

1. 查找左端点

定义 left 和 right 指针。
初始化 begin = -1（表示左端点索引）。
进入循环，条件为 left <= right：
- 计算 mid = left + (right - left) / 2。
- 如果 arr[mid] >= target，说明左端点可能是 mid 或在其左侧，更新 right = mid - 1。
- 如果 arr[mid] < target，说明左端点在右侧，更新 left = mid + 1。
循环结束后，如果 arr[left] == target，说明找到左端点，begin = left；否则返回 -1。

2. 查找右端点

重新定义 left 和 right 指针。
初始化 end = -1（表示右端点索引）。
进入循环，条件为 left <= right：
- 使用 避免死循环 的方式计算中间点：mid = left + (right - left + 1) / 2。
- 如果 arr[mid] <= target，说明右端点可能是 mid 或在其右侧，更新 left = mid。
- 如果 arr[mid] > target，说明右端点在左侧，更新 right = mid - 1。
循环结束后，如果 arr[right] == target，说明找到右端点，end = right；否则返回 -1。

返回区间

最终返回区间 [begin, end]：

如果 begin == -1，说明目标值不存在，返回空区间。

实现代码

pair<int, int> findRange(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    int begin = -1, end = -1;

    // 查找左端点
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) {
            right = mid - 1;
            if (arr[mid] == target) {
                begin = mid; // 更新左端点
            }
        } else {
            left = mid + 1;
        }
    }

    // 查找右端点
    left = 0, right = arr.size() - 1; // 重置指针
    while (left <= right) {
        int mid = left + (right - left + 1) / 2; // 避免死循环
        if (arr[mid] <= target) {
            left = mid;
            if (arr[mid] == target) {
                end = mid; // 更新右端点
            }
        } else {
            right = mid - 1;
        }
    }

    return {begin, end}; // 返回区间
}

示例用法

假设有以下有序数组：

vector<int> arr = {1, 2, 2, 2, 3, 4, 5};
int target = 2;

// 普通二分查找
int index = binarySearch(arr, target);
cout << "Index: " << index << endl; // 输出: 2（数组中第一个 2 的索引）

// 查找区间
pair<int, int> range = findRange(arr, target);
cout << "Range: [" << range.first << ", " << range.second << "]" << endl;
// 输出: [1, 3] （target 值 2 在数组中的范围）

3. 常见问题与优化

整数溢出：使用 mid = left + (right - left) / 2 避免直接 (left + right) / 2 导致溢出。
循环死锁：
- 查找右端点时，采用 mid = left + (right - left + 1) / 2，确保更新 left 时不会进入死循环。
查找边界值：如果需要查找小于等于（或大于等于）目标值的边界，注意使用不同的更新逻辑。