二分查找算法原理与实战应用

二分查找

1. 含义

二分查找（Binary Search）是一种高效的查找算法，核心是每次将查找范围减半，仅适用于已排序的数组或区间，时间复杂度为 O(log n)。

2. 操作过程

以在一个升序数组中查找一个数为例。它每次考察数组当前部分的中间元素：

• 如果中间元素刚好是要找的，结束搜索；
• 如果中间元素小于所查找的值，左侧只会更小，只需到右侧查找；
• 如果中间元素大于所查找的值，只需到左侧查找。

3. 前提

数据必须有序。

4. 基础代码示例

int bs(vector<int>& a, int n, int target) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] == target) {
            return mid; // 无重复目标值时
        } else if (a[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return -1;
}

二分答案（猜答案）

1. 做题步骤

确定题目适合二分 -> 确定答案的范围 -> 假定一个解判断是否可行。

2. 题目类型

最值问题（可能要用二分），例如最小化最大值以及最大化最小值问题（大概率用二分）。

3. 例题 1

题目描述：给定 n 棵树的高度，求一个最大的参数值 h，使他把所有树 h 以上的部分砍掉以后，能得到 m 米或者以上的木材。换句话说，如果再升高 1 米，他将得不到 M 米木材。 思路：二分树的高度 0-400000，然后在 check 函数中去判断是否可行，即算一下得到的木材是否满足 m。 参考题目：洛谷 P1873

#include<iostream>
#include<limits>





  std;

{
     sum = ;
     n = a.();
     ( i = ; i < n; i++) {
         (a[i] > mid) {
            sum += a[i] - mid;
        }
    }
     (sum >= m) {
         ;
    }  {
         ;
    }
}

{
     n, m;
    cin >> n >> m;
    ;
     ( i = ; i < n; i++) {
        cin >> h[i];
    }
     l = , r = , ans = ;
     (l <= r) {
         mid = (l + r) / ;
         ((mid, h, m)) {
            l = mid + ;
            ans = mid;
        }  {
            r = mid - ;
        }
    }
    cout << ans << endl;
}

{
    ios::(), cin.(), cout.();
     t;
    cin >> t;
     (t--) {
        ();
    }
     ;
}