二分查找

->返回c/c++蓝桥杯经典编程题100道-目录

---

目录

二分查找

一、题型解释

二、例题问题描述

三、C语言实现

解法1：基础二分查找（难度★）

解法2：左边界查找（难度★★）

解法3：旋转数组查找（难度★★★）

四、C++实现

解法1：STL的binary_search（难度★）

解法2：自定义左边界查找（难度★★）

解法3：峰值查找（难度★★★）

五、总结对比表

---

一、题型解释

二分查找是一种在 有序数组 中快速查找目标值的高效算法。常见题型：

1. 基础查找：在有序数组中判断目标值是否存在。

2. 边界查找：

   • 查找目标值的 第一个出现位置（左边界）。

   • 查找目标值的 最后一个出现位置（右边界）。

3. 旋转数组查找：在部分有序的旋转数组中查找目标值。

4. 峰值查找：在无序数组中找到任意一个峰值元素（比相邻元素大）。

---

二、例题问题描述

例题1：输入有序数组 [1, 3, 5, 7, 9] 和目标值 5，输出 true（存在）。
例题2：输入数组 [1, 2, 2, 2, 3] 和目标值 2，输出左边界 1 和右边界 3。
例题3：输入旋转数组 [4, 5, 6, 7, 0, 1, 2] 和目标值 0，输出位置 4。
例题4：输入数组 [1, 3, 5, 4, 2]，输出任意一个峰值元素的索引（如 2 或 3）。

---

三、C语言实现

解法1：基础二分查找（难度★）

通俗解释：

• 像猜数字游戏，每次猜中间数，缩小一半范围。

c

#include <stdio.h>

int binarySearch(int arr[], int n, int target) {
    int left = 0, right = n - 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; // 未找到
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int target = 5;
    int index = binarySearch(arr, 5, target);
    printf("目标值位置：%d", index); // 输出 2
    return 0;
}

代码逻辑：

1. 初始化范围：left 和 right 分别指向数组首尾。

2. 计算中间点：mid = left + (right - left)/2（避免 (left+right) 溢出）。

3. 比较与调整：

   • 若 arr[mid] == target，直接返回位置。

   • 若 arr[mid] < target，说明目标在右半部分，调整 left = mid + 1。

   • 否则调整 right = mid - 1。

4. 终止条件：当 left > right 时说明未找到，返回 -1。

---

解法2：左边界查找（难度★★）

通俗解释：

• 找到第一个等于目标值的元素，即使有重复元素。

c

int leftBound(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {     // 目标在右半部分
            left = mid + 1;
        } else {                     // 目标在左半部分或等于
            right = mid - 1;         // 向左收缩右边界
        }
    }
    // 检查 left 是否越界或找到目标
    if (left >= n || arr[left] != target) return -1;
    return left;
}

int main() {
    int arr[] = {1, 2, 2, 2, 3};
    int target = 2;
    printf("左边界：%d", leftBound(arr, 5, target)); // 输出 1
    return 0;
}

代码逻辑：

1. 调整策略：当 arr[mid] >= target 时，继续向左收缩右边界。

2. 最终定位：循环结束后，left 指向第一个等于目标的位置（需检查有效性）。

---

解法3：旋转数组查找（难度★★★）

通俗解释：

• 在“折断”的有序数组中，分情况判断目标在左半还是右半。

c

int searchRotated(int arr[], int n, int target) {
    int left = 0, right = n - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        // 判断左半部分是否有序
        if (arr[left] <= arr[mid]) { 
            if (arr[left] <= target && target < arr[mid]) { // 目标在左半
                right = mid - 1;
            } else { // 目标在右半
                left = mid + 1;
            }
        } else { // 右半部分有序
            if (arr[mid] < target && target <= arr[right]) { // 目标在右半
                left = mid + 1;
            } else { // 目标在左半
                right = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    int arr[] = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;
    printf("位置：%d", searchRotated(arr, 7, target)); // 输出 4
    return 0;
}

代码逻辑：

1. 判断有序部分：根据 arr[left] 和 arr[mid] 的关系，确定左半或右半是否有序。

2. 调整搜索范围：根据目标值是否在有序部分内，调整 left 或 right。

---

四、C++实现

解法1：STL的binary_search（难度★）

通俗解释：

• 直接使用标准库函数判断目标是否存在。

cpp

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

int main() {
    vector<int> vec = {1, 3, 5, 7, 9};
    int target = 5;
    bool found = binary_search(vec.begin(), vec.end(), target);
    cout << "是否存在：" << found; // 输出 1（true）
    return 0;
}

代码逻辑：

1. binary_search函数：

   • 参数1：起始迭代器。

   • 参数2：结束迭代器。

   • 参数3：目标值。

   • 返回布尔值表示是否存在。

---

解法2：自定义左边界查找（难度★★）

通俗解释：

• 使用STL的 lower_bound 函数快速定位左边界。

cpp

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

int main() {
    vector<int> vec = {1, 2, 2, 2, 3};
    int target = 2;
    auto it = lower_bound(vec.begin(), vec.end(), target); // 找第一个 >= target的位置
    if (it != vec.end() && *it == target) {
        cout << "左边界：" << it - vec.begin(); // 输出 1
    } else {
        cout << "未找到";
    }
    return 0;
}

代码逻辑：

1. lower_bound函数：

   • 返回第一个 大于等于 目标值的迭代器。

   • 若找到且值等于目标，则为左边界。

---

解法3：峰值查找（难度★★★）

通俗解释：

• 像爬山找顶峰，只要发现上坡，顶峰一定在右边。

cpp

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

int findPeak(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) { // 注意条件不是 <=
        int mid = left + (right - left) / 2;
        if (nums[mid] < nums[mid + 1]) { // 上坡，顶峰在右侧
            left = mid + 1;
        } else { // 下坡或顶峰，向左收缩
            right = mid;
        }
    }
    return left; // left == right 时为峰值位置
}

int main() {
    vector<int> nums = {1, 3, 5, 4, 2};
    cout << "峰值索引：" << findPeak(nums); // 输出 2（对应5）
    return 0;
}

代码逻辑：

1. 比较相邻元素：若 nums[mid] < nums[mid+1]，说明右侧存在更高点。

2. 调整范围：

   • 上坡时，left = mid + 1。

   • 否则，right = mid（可能为峰值）。

---

五、总结对比表

方法	时间复杂度	空间复杂度	优点	缺点
基础二分查找	O(log n)	O(1)	简单高效	仅适用于有序数组
左/右边界查找	O(log n)	O(1)	处理重复元素	需理解边界收缩逻辑
旋转数组查找	O(log n)	O(1)	处理部分有序数组	逻辑复杂，需分情况讨论
STL函数	O(log n)	O(1)	代码极简	依赖STL
峰值查找	O(log n)	O(1)	无需完全有序	仅适用于特定问题

->返回c/c++蓝桥杯经典编程题100道-目录