登录以参加训练计划

二分查找算法

一、基础知识

1. 基本概念

• 定义：二分查找是一种在有序数组中查找特定元素的算法，每次比较中间元素，并根据比较结果缩小搜索范围。
• 时间复杂度：O(log n)，其中n是数组长度。
• 空间复杂度：O(1)（迭代实现），O(log n)（递归实现，考虑调用栈）。

2. 适用条件

• 数组必须有序：二分查找依赖于数组的有序性。如果数组无序，必须先排序。
• 随机访问：需要能够通过索引直接访问数组中的任意元素。

二、实现方法

1. 迭代实现

int binarySearchIterative(int arr[], int l, int r, int x) {
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) return mid; // 找到目标值
        if (arr[mid] < x) l = mid + 1; // 在右半部分继续查找
        else r = mid - 1;              // 在左半部分继续查找
    }
    return -1; // 没有找到目标值
}

2. 递归实现

int binarySearchRecursive(int arr[], int l, int r, int x) {
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x) return mid; // 找到目标值
        if (arr[mid] > x) return binarySearchRecursive(arr, l, mid - 1, x); // 在左半部分继续查找
        return binarySearchRecursive(arr, mid + 1, r, x); // 在右半部分继续查找
    }
    return -1; // 没有找到目标值
}

三、注意事项

1. 边界条件

• 初始化边界：确保 l 和 r 的初始值正确。通常 l 初始化为0，r 初始化为数组长度减1。
• 循环终止条件：当 l 超过 r 时，表示没有找到目标值。

2. 防止溢出

• 计算中间位置：避免直接使用 (l + r) / 2，因为这可能导致整数溢出。应使用 l + (r - l) / 2 或 l + ((r - l) >> 1) 来计算中间位置。

3. 处理重复元素

• 如果数组中有重复元素，二分查找可能返回任何一个匹配的索引。如果需要找到第一个或最后一个匹配的元素，需要额外处理。

四、扩展应用

1. 最大化最小值/最小化最大值问题

• 应用场景：如本题中的奶牛问题，需要在一定范围内寻找最优解，满足某种约束条件。
• 实现方式：通过二分查找尝试不同的距离或其他数值，结合辅助函数验证可行性。

2. 查找上下界

• 查找第一个大于等于目标值的位置：

  int lowerBound(int arr[], int n, int x) {
      int l = 0, r = n - 1;
      while (l <= r) {
          int mid = l + (r - l) / 2;
          if (arr[mid] < x) l = mid + 1;
          else r = mid - 1;
      }
      return l;
  }
  

• 查找最后一个小于等于目标值的位置：：

int upperBound(int arr[], int n, int x) {
    int l = 0, r = n - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (arr[mid] <= x) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}

五、经典使用场景

1. 查找特定值

• 应用场景：在一个有序数组中查找某个特定值。
• 例子：查找学生成绩表中某个学生的成绩。

2. 查找上下界

• 应用场景：查找某个值的插入位置，或者查找某个范围内的所有元素。
• 例子：查找商品价格区间内的所有商品。

3. 最大化最小值/最小化最大值

• 应用场景：分配任务、资源调度等问题。
• 例子：分配机器给工人，使得最忙的工人工作量最小；分配任务给服务器，使得最慢的服务器完成时间最短。

4. 求平方根

• 应用场景：计算一个数的平方根，精确到一定的精度。
• 例子：计算 sqrt(x)。

5. 查找旋转排序数组中的最小值

• 应用场景：在一个经过旋转的有序数组中查找最小值。
• 例子：LeetCode 153: Find Minimum in Rotated Sorted Array

以下是二分答案：

六，典型题分析：

（1）二分查找的五种核心变种及其原理

1. 普通二分查找（任意匹配位置）

​​目标​​：找到数组中任意一个等于目标值的位置。

int binary_search(int x) {
    int l = 1, r = n;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] == x) return mid; // 直接返回匹配位置
        else if (a[mid] < x) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

2. 左侧边界查找（第一个等于目标值的位置）

​​目标​​：找到数组中第一个等于目标值的位置。

int left_bound(int x) {
    int l = 1, r = n;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid - 1; // 向左收缩
        else l = mid + 1;
    }
    if (l <= n && a[l] == x) return l;
    else return -1;
}

3. 右侧边界查找（最后一个等于目标值的位置）

​​目标​​：找到数组中最后一个等于目标值的位置。

int right_bound(int x) {
    int l = 1, r = n;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (a[mid] <= x) l = mid + 1; // 向右收缩
        else r = mid - 1;
    }
    if (r >= 1 && a[r] == x) return r; // 检查r的位置
    else return -1;
}

4.第一个大于等于x的元素。

​​目标​​：找到数组中第一个大于等于目标值的位置。

int first_ge(int x) {
    int l = 1, r = n;
    while (l <= r) {
        int mid = l + (r - l)/2;
        if (a[mid] >= x) r = mid - 1; // 向左收缩
        else l = mid + 1;
    }
    return (l <= n) ? l : -1;
}

5.最后一个小于等于x的元素。

​​目标​​：找到数组中最后一个小于等于目标值的位置。

int first_ge(int x) {
    int l = 1, r = n;
    while (l <= r) {
        int mid = l + (r - l)/2;
        if (a[mid] <= x) l = mid + 1; // 向右收缩
        else r = mid - 1;
    }
    return (r >= 1) ? r : -1;
}

6.最接近x的元素（绝对值最小）。

​​目标​​：找到数组中与目标值最接近的数的位置。

int first_ge(int x) {
    int l = 1, r = n;
    while (l < r-1) { // 留两个元素比较
        int mid = l + (r - l)/2;
        if (a[mid] <= x) l = mid; 
        else r = mid;
    }
    // 比较l和r位置的值
    if (abs(a[l] - x) <= abs(a[r] - x)) return l;
    else return r;
}

7. 通用解题技巧

​​循环条件​​：统一使用 while (l <= r)，避免死循环。 ​​中间值计算​​：使用 mid = l + (r - l)/2 防止溢出。 ​​边界移动​​：根据比较结果决定收缩左或右区间。 ​​最终验证​​：循环结束后需检查位置合法性。 ​​索引处理​​：注意题目中数组起始位置（从0还是1开始）。

二分答案？

​​二分答案​​ 是一种利用二分查找思想解决 ​​最优化问题​​ 的方法。它通常用于解决以下类型的问题：

• ​​最小值最大化​​（如：在限制条件下，求最小的最大值）
• ​​最大值最小化​​（如：在限制条件下，求最大的最小值）
• ​​可行性判断​​（如：判断某个条件是否能被满足）

其核心思想是 ​​通过二分法在候选答案的范围内，快速找到满足条件的最优解​​。

---

1、二分答案 vs 普通二分查找

对比维度	普通二分查找	二分答案
​​适用场景​​	在有序数组中查找特定元素的位置	在连续的解空间中寻找满足条件的最优解
​​问题类型​​	精确匹配（存在性问题）	最优化问题（最大/最小值问题）
​​候选解范围​​	离散（数组索引）	连续（数值范围，如 [0, 1e9]）
​​关键操作​​	比较 a[mid] 和目标值的大小	验证中间值是否满足条件，调整搜索区间

---

2、二分答案的步骤

1. ​​确定答案范围​​
   找到候选答案的最小值 left 和最大值 right（如：问题可能解的最小和最大值）。

2. ​​二分搜索​​
   在 [left, right] 范围内，通过不断二分中间值 mid，验证 mid 是否满足条件。

3. ​​调整区间​​

   • 如果 mid 可行，尝试寻找更优解（如：更大的最小值或更小的最大值）。
   • 如果 mid 不可行，排除无效区间。

4. ​​终止条件​​
   当 left > right 时结束，此时 left 或 right 即为最优解。

---

3、经典例题：木材切割问题

问题描述

给定 n 根原木，每根长度为 L[i]，需要将它们切割成至少 k 段。求每段的最大可能长度。

解法分析

1. ​​确定候选范围​​

   • 最小长度 left = 1（至少切 1 单位）
   • 最大长度 right = max(L)（不切割时的最大长度）

2. ​​验证函数设计​​
   对于给定的长度 mid，判断是否能切出至少 k 段：

   bool check(int mid, vector<int>& L, int k) {
       int cnt = 0;
       for (int l : L) cnt += l / mid; // 每根能切多少段
       return cnt >= k;
   }

3. ​​二分答案​​

int max_length(vector<int>& L, int k) {
    int left = 1, right = *max_element(L.begin(), L.end());
    int ans = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(mid, L, k)) {
            ans = mid;       // 当前mid可行，尝试更大的值
            left = mid + 1;
        } else {
            right = mid - 1; // 当前mid太小，缩小右边界
        }
    }
    return ans;
}

4、适用条件

1. 单调性

• 问题的解在候选范围内具有​​单调性​​
  例如：若 mid 可行，则比 mid 小（或大）的值也一定可行。

2. 可验证性

• 能快速判断某个候选值 mid 是否满足条件
  （需设计高效的 check 函数，时间复杂度通常为 O(n) 或 O(n log n)）

---

5、常见题型

1. 最值问题

• ​​最小化最大值​​
  示例：分配任务使最大负载最小
• ​​最大化最小值​​
  示例：安排广告牌使最小间距最大

2. 可行性问题

• ​​条件判断​​
  示例：判断是否能在 D 天内运完货物

3. 数学问题

• ​​方程近似解​​
  示例：求平方根、立方根的近似值

---

6、总结

​​二分答案​​ 是将二分查找思想应用于最优化问题的高效方法，核心要点如下：

1. ​​缩小解空间​​

   • 确定候选解的上下界 [left, right]
   • 初始范围需覆盖所有可能解

2. ​​高效验证​​

   • 设计时间复杂度低的 check 函数
   • 示例：木材切割问题的 check 函数时间复杂度为 O(n)

3. ​​动态调整区间​​

   • 根据验证结果收缩左/右边界
   • 终止条件：left > right

​​核心优势​​：将最优化问题的时间复杂度从 O(n^2) 优化至 ​​O(n log C)​​，其中 C 为候选解范围大小。