算法精讲：二分查找（二）—— 变形技巧

🎯 算法精讲：二分查找（二）—— 变形技巧 🔍

友情提示：：本小节含高能代码片段 🥤

1. 阅读前请确保已掌握基础二分原理与实现
2. 代码片段可能包含不同程度的变形，请根据实际情况选择阅读

作者：无限大

推荐阅读时间：30min

📚 内容回顾与引言

在上一篇《算法精讲：二分查找（一）—— 基础原理与实现》中，我们剖析了二分查找的核心原理：依赖有序数组的单调性，通过不断折半搜索快速定位目标值 📈。

重点讲解了两大区间定义方式（左闭右闭 [left, right] 与左闭右开 [left, right)）及其代码实现细节，并强调了循环不变量原则的重要性。

如果说基础二分是少林长拳，那各种变形就是奇门遁甲！本篇我们将解锁二分查找的 “高阶技能”，解锁二分查找的隐藏皮肤 🧥！从基础的边界值变形（如找第一个/最后一个等于目标值的位置）到复杂场景应用（如旋转数组、珂珂吃香蕉问题）。

🧩 一、常见二分变形及应用场景

1. 查找第一个等于目标值的元素位置

思路：在非递减序列中查找第一个等于目标值的元素。当 arr[mid] == target 时，不立即返回，而是继续向左查找（即 right = mid - 1），以确保找到的是第一个出现的位置。

代码实现：

/**
 * 在含重复元素的有序数组中，找到目标值第一次出现的位置
 * @param nums 有序数组（可重复）
 * @param target 目标值
 * @return 首个等于target的索引，未找到返回-1
 */
public int findFirstEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int result = -1; // 初始化结果

    while (left <= right) {
        int mid = left + (right - left) / 2; // 防溢出计算中点

        if (nums[mid] == target) {
            result = mid;    // 记录位置
            right = mid - 1; //  👉 关键！继续向左搜索更早出现的目标
        } else if (nums[mid] < target) {
            left = mid + 1;  // 目标在右半区
        } else {
            right = mid - 1; // 目标在左半区
        }
    }
    return result; // 返回首个位置
}

✅ 适用场景：统计数字 4 在数组 [1,2,4,4,4,5] 中的起始位置（返回 2）

2. 查找第一个大于等于目标值的元素位置

思路：
目标是找到第一个大于或等于目标值的元素。当 arr[mid] >= target 时，缩小右边界（right = mid - 1），否则缩小左边界（left = mid + 1）。循环结束后，直接返回 left，因为它指向第一个大于等于目标值的位置。

代码实现：

/**
 * 找到有序数组中首个≥target的元素位置
 * @param nums 有序数组
 * @param target 目标值
 * @return 首个≥target的索引（若target超最大值返回-1）
 */
public int findFirstGreaterOrEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

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

        if (nums[mid] >= target) {
            right = mid - 1; //  👉 向左收缩，尝试找到更小的满足条件的值
        } else {
            left = mid + 1;  // 向右扩大搜索
        }
    }
    // 结束时left指向首个≥target的位置
    return (left < nums.length) ? left : -1;
}

✅ 典型应用：将数字 3 插入有序数组 [1,2,4,5] 的正确位置（返回 2）

3. 查找第一个大于目标值的元素位置

思路：
寻找第一个大于目标值的元素。当 arr[mid] <= target 时，缩小左边界（left = mid + 1），否则缩小右边界（right = mid - 1）。循环结束后，left 指向第一个大于目标值的元素。

/**
 * 找到有序数组中首个>target的元素位置
 * @param nums 有序数组
 * @param target 目标值
 * @return 首个>target的索引（若target超最大值返回-1）
 */
public int findFirstGreater(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

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

        if (nums[mid] <= target) { //  👉 注意条件包含等于
            left = mid + 1;  // 目标在右半区
        } else {
            right = mid - 1; // 向左收缩
        }
    }
    return (left < nums.length) ? left : -1;
}

💡 关键点：当 nums[mid] == target 时仍需右移，确保定位到严格大于的位置

4. 查找最后一个等于目标值的元素位置

思路：
在非递减序列中查找最后一个等于目标值的元素。当 arr[mid] == target 时，不立即返回，而是继续向右查找（即 left = mid + 1），以确保找到的是最后一个出现的位置。循环结束后，检查 right 是否越界以及 arr[right] 是否等于目标值。

/**
 * 在含重复元素的有序数组中，找到目标值最后一次出现的位置
 * @param nums 有序数组
 * @param target 目标值
 * @return 最后一个等于target的索引，未找到返回-1
 */
public int findLastEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int result = -1;

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

        if (nums[mid] == target) {
            result = mid;   // 记录位置
            left = mid + 1; //  👉 关键！继续向右搜索更晚出现的目标
        } else if (nums[mid] < target) {
            left = mid + 1; // 目标在右半区
        } else {
            right = mid - 1;// 目标在左半区
        }
    }
    return result;
}

✅ 用例：确定 4 在 [1,2,4,4,4,5] 中的结束位置（返回 4）

5. 查找最后一个小于等于目标值的元素位置

思路：
目标是找到最后一个小于等于目标值的元素。当 arr[mid] <= target 时，缩小左边界（left = mid + 1），否则缩小右边界（right = mid - 1）。循环结束后，right 指向最后一个小于等于目标值的元素。

/**
 * 找到有序数组中最后一个≤target的元素位置
 * @param nums 有序数组
 * @param target 目标值
 * @return 最后一个≤target的索引（若target小于最小值返回-1）
 */
public int findLastLessOrEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int result = -1;

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

        if (nums[mid] <= target) {
            result = mid;     // 记录可能位置
            left = mid + 1;   // 👉 向右尝试找到更大的满足值
        } else {
            right = mid - 1;  // 目标在左半区
        }
    }
    return result;
}

💡 应用场景：统计考试成绩 ≤80 分的最高分学生位置

6. 查找最后一个小于目标值的元素位置

思路：
寻找最后一个小于目标值的元素。当 arr[mid] < target 时，缩小左边界（left = mid + 1），否则缩小右边界（right = mid - 1）。循环结束后，right 指向最后一个小于目标值的元素。

代码实现：

/**
 * 找到有序数组中最后一个<target的元素位置
 * @param nums 有序数组
 * @param target 目标值
 * @return 最后一个<target的索引（若target小于最小值返回-1）
 */
public int findLastLess(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    int result = -1;

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

        if (nums[mid] < target) {
            result = mid;     // 记录位置
            left = mid + 1;   //  👉 向右尝试找到更大的满足值
        } else {
            right = mid - 1;  // 目标在左半区
        }
    }
    return result;
}

✅ 典型场景：在 [10,20,30,40] 中找 <35 的最后位置（返回 2）

六种核心变形对比

💡 核心区别：普通二分找到目标即返回，而变形算法会继续向特定方向收缩边界，确保定位到最左/最右的目标值

⚠️ 边界处理避坑指南

二分变形代码的 “魔鬼在细节”，90%的 bug 源于边界处理不当！以下是四大核心避坑点：

1. 初始边界设置原则

• 右边界取值：
  • right = length - 1 ➜ 闭区间搜索（如普通二分）
  • right = length ➜ 开区间搜索（如插入位置问题），防止漏检末尾元素

示例：

// 闭区间：搜索范围[0, length-1]
int right = nums.length - 1;
// 开区间：搜索范围[0, length)
int right = nums.length;

2. 循环条件选择策略

黄金法则：

• 用 <=时必须配合 left=mid+1/right=mid-1
• 用 <时必须配合 left=mid+1/right=mid

3. 越界处理技巧

• 返回前必校验：

  // 检查left是否越界（开区间场景）
  return (left < nums.length) ? left : -1;
  

• 防 off-by-one 错误：

  • 当 left=0或 right=length-1时，mid计算需防溢出 ➜ mid = left + (right - left) / 2

  • 结束时验证结果有效性：

    // 查找类需验证找到的是否为目标值
    if (left >= nums.length || nums[left] != target) return -1;
    

温馨提示

在编程中，off-by-one（差一错误） 指因边界处理偏差导致的逻辑错误，通常表现为循环、索引或区间计算中意外地少或多一次操作。这种错误在二分查找中尤为常见，可能导致死循环、漏检或越界崩溃。

4. 重复元素特判

当数组含重复值时，额外添加分支：

// 旋转数组场景（解决 [3,1,2,3,3,3,3] 类问题）
if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
    left++;   // 跳过左侧重复
    right--;  // 跳过右侧重复
}

💡 边界心法口诀：

初值定区间 → 循环控方向 → 退出验边界 → 重复要特判

掌握此四步，二分无坑！ 🔥

🚀 二、二分变形之魂：LeetCode 实战 ️

光说不练假把式，来点硬菜！

案例 1：珂珂吃香蕉（LeetCode 875）

题目：传送门

场景：珂珂面前堆着 N堆香蕉，警卫 H小时后回来。她每小时只能选一堆吃 K根，吃不完藏枕头下。求最小吃速 K让她优雅吃完蕉。

场景翻译：
当你妈出门时说「H 小时后回来」👩，而你要偷吃掉 N 堆香蕉 🍌…每堆数量随机！每小时只能选一堆吃 K 根（不够还得藏枕头下），求最小吃速 K避免被打 👋

解题思路拆解：

1.为什么用二分：

• 吃速 K存在临界点：小于它吃不完（太淑女），大于它浪费（变饭桶）

• 暴力枚举会超时 → 二分搜索完美匹配"找最小可行解"场景

  2.灵魂三问：

• 搜索区间：[1, 最大香蕉堆]（吃速至少为 1，最大不超过最大堆）

• 判断条件：当前吃速mid能否在H小时内吃完 ✅

• 边界收缩：能吃完就压榨吃速（right=mid-1），吃不完就加速（left=mid+1）

二分妙用：

public int minEatingSpeed(int[] piles, int h) {
    int left = 1; // 吃速下限：淑女的矜持（至少1根/小时）
    int right = 0;
    for (int pile : piles) right = Math.max(right, pile); //  👉 最大堆即吃速上限

    // 🔥 二分奥义：在[1,最大堆]区间反复横跳测试，看看哪个速度能吃完香蕉
    while (left <= right) {
        int mid = left + (right - left) / 2; // mid=当前测试吃速
        if (canFinish(piles, mid, h)) {
            right = mid - 1; //  🙆♀️ 能吃完？再压榨下吃速！
        } else {
            left = mid + 1; //  🙅♂️ 吃不完？加速干饭！
        }
    }
    return left; // 返回最小吃速K
}

private boolean canFinish(int[] piles, int speed, int h) {
    int hoursNeeded = 0;
    for (int pile : piles) {
        // ✨ 骚操作：整数除法向上取整（pile+speed-1）相当于数学ceil()
        hoursNeeded += (pile + speed - 1) / speed;
        if (hoursNeeded > h) return false; //  ⌛ 超时警告
    }
    return true;
}

关键点：

1.mid 是当前测试的吃香蕉速度

2.canEatAll 返回 true → 还能压榨更小 K！（收缩右边界）

3.搜索区间右边界初始化为 max(piles)而非固定值，更通用

关键技巧：

🌀 案例 2：旋转数组搜索（LeetCode 33）🎡

题目：传送门

场景：数组 [0,1,2,4,5,6,7]旋转后变 [4,5,6,7,0,1,2]，如何在旋转数组中搜 target？

破局点：旋转后必有一半有序！记住这个黄金定律

代码的艺术：

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid; //   欧皇附体

        // 左半边有序情景 [4,5,6,7,...]
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1; //  👈 target在有序左半区
            } else {
                left = mid + 1; //  👉 目标在混乱右半区
            }
        }
        // 右半边有序情景 [...,0,1,2]
        else {
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1; // 👉 target在有序右半区
            } else {
                right = mid - 1; // 👈 目标在混乱左半区
            }
        }
    }
    return -1; //  😭 非酋结局
}

精髓：

• 先判断哪半边有序 🔍
• 再判断 target 是否在有序区间内

避坑指南：

• 比较时用<=而不是<，处理重复元素边界

• 判断有序区间时，nums[left] <= nums[mid]中的=处理单元素情况

• 乱中有序，二分永不为奴！

💎 三、二分终极奥义：抽象建模大法 🌌

你以为二分只能搜数组？Noooo，格局打开！凡是能分成两段性的问题，皆可二分！

万能二分模板（背会秒杀 80%题）✍️

while (left <= right) {
    int mid = left + (right - left) / 2; // 防溢出
    if (condition(mid)) {
        right = mid - 1; // 向左侧探索
    } else {
        left = mid + 1; // 向右侧探索
    }
}
return left; // 魔法值：可能是解/插入位置

四大抽象场景总结 🧩

🏁 四、课后作业大礼包 📚

1. 基础篇：34. 在排序数组中查找元素的第一个和最后一个位置

题目：

给定升序数组`nums`和目标值`target`，返回`target`的起始和终止位置，不存在则返回`[-1,-1]`  
示例：  
输入：`nums = [5,7,7,8,8,10], target = 8`  
输出：`[3,4]`

通关秘籍：

• 组合拳：findFirstEqual + findLastEqual 双剑合璧
• 注意处理target不存在时的边界检查

2. 进阶篇：162. 寻找峰值

烧脑点：

• 数组未经排序 → 利用相邻元素比较确定趋势
• 关键代码：

if (nums[mid] < nums[mid + 1]) {
    left = mid + 1; //  📈 上升趋势，峰值在右
} else {
    right = mid; // 📉 下降趋势，峰值在左
}

3. 地狱篇：410. 分割数组的最大值

终极奥义：

while (left <= right) {
    int mid = (left + right) / 2;
    if (canSplit(nums, mid, m)) { // 判断是否能分成m段且每段和<=mid
        right = mid - 1; // 能分割，尝试更小的最大值
    } else {
        left = mid + 1; // 不能分割，增大最大值
    }
}
return left; // 最小化最大分段和

💡 多语言提示：

• Python：mid = (left + right) // 2（注意整数除法）。
• C++：使用mid = left + (right - left) / 2防溢出。

灵魂画手：

数组: [7,2,5,10,8]  m=2
最小最大和：18 →  [7,2,5] 和 [10,8]

本篇关键收获

• 变形本质：普通二分找到即返回，变形需向特定方向收缩边界（左/右）。

• 抽象心法：凡问题具两段性（如可行/不可行分界），皆可二分。

• 必记技巧：防溢出中点计算、循环不变量维护。

✨ 无限大忠告：把代码复制到 IDE，开启调试模式观察边界变化！

遇到 bug 时：

1. 喝口水 ☕

2. 画边界图 📊

3. 默念"循环不变量"三遍 🧘

4. 点这里看解法（别真点，自己思考！）

5. 欢迎各位在评论区分享你的解题思路！

（未完待续：下一篇预告《二分的时空幻术——复杂度与优化篇》）🔥