二分查找概念

概述

这里我简略提一下
详细版的看这个博客链接csdn
b站讲解

1. 什么是二分查找（Binary Search）

核心思想一句话：👉 每次把搜索范围缩小一半

二分查找是一种在有序数组中查找元素的高效算法。

✅ 前提条件

• 数据必须是有序的（升序或降序）
• 能够通过“大小关系”判断方向

🧠 基本思路

假设在升序数组中找 target：

1. 取中间位置 mid

2. 比较：

3. a[mid] == target → 找到了 ✅

4. a[mid] < target → 去右边找
5. a[mid] > target → 去左边找
6. 重复直到找到或区间为空

📌 时间复杂度

• 时间复杂度：O(log n)
• 比线性查找 O(n) 快很多

---

2. C语言实现

#include <stdio.h>

int binary_search(int a[], int n, int target) {
    int left = 0, right = n - 1;

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

        if (a[mid] == target) {
            return mid;  // 返回下标
        } else if (a[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;  // 没找到
}

int main() {
    int a[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(a) / sizeof(a[0]);
    int target = 7;

    int pos = binary_search(a, n, target);

    if (pos != -1)
        printf("找到，下标 = %d\n", pos);
    else
        printf("未找到\n");

    return 0;
}

3. C++实现

#include <iostream>
using namespace std;

int binarySearch(int a[], int n, int target) {
    int left = 0, right = n - 1;

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

        if (a[mid] == target) return mid;
        else if (a[mid] < target) left = mid + 1;
        else right = mid - 1;
    }

    return -1;
}

int main() {
    int a[] = {1, 3, 5, 7, 9, 11};
    int n = sizeof(a) / sizeof(a[0]);

    int pos = binarySearch(a, n, 7);

    if (pos != -1) cout << "找到，下标 = " << pos;
    else cout << "未找到";

    return 0;
}

---

4. 进阶：二分查找的两种常见变形

1️⃣ 查找左边界（lower_bound）

👉 找 第一个 ≥ target 的位置

int left_bound(int a[], int n, int target) {
    int left = 0, right = n - 1, ans = n;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (a[mid] >= target) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

---

2️⃣ 查找右边界（upper_bound）

👉 找 最后一个 ≤ target 的位置

int right_bound(int a[], int n, int target) {
    int left = 0, right = n - 1, ans = -1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (a[mid] <= target) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
}

---

5. 经典应用实例（重点🔥）

📌 例题：查找某个数是否存在

题目

给定一个升序数组，查询某个数是否存在。

输入

n = 6
a = [1,3,5,7,9,11]
target = 9

输出

存在，下标 = 4

👉 直接用基础二分即可（上面代码）

---

🎯 例子：最小满足条件的值

题目： 给你一个数组，每个数代表工作量，要求在 k 天内完成，问每天最少做多少？

👉 本质：

• 答案范围是 [max(a), sum(a)]
• 判断函数：是否能在 k 天完成

💡 C++代码

#include <iostream>
using namespace std;

bool check(int a[], int n, int k, int limit) {
    int days = 1, sum = 0;

    for (int i = 0; i < n; i++) {
        if (sum + a[i] > limit) {
            days++;
            sum = a[i];
        } else {
            sum += a[i];
        }
    }

    return days <= k;
}

int main() {
    int a[] = {7, 2, 5, 10, 8};
    int n = 5, k = 2;

    int left = 10, right = 32, ans = 0;

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

        if (check(a, n, k, mid)) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << "最小值 = " << ans;
}

---

6. 总结

• 二分查找 = 每次砍一半
• 前提：有序

• 核心变量：

• left, right, mid

• 三种类型：

• 普通查找

• 左边界 / 右边界
• 🔥 答案二分（最重要）

---