编程导航会员会员
登录/注册

二分法（含 gift 演示）


二分法


二分法原理很简单，但是细节是魔鬼


寻找一个数


当我们使用 while 循环条件是 left <= right 的时候，我们的最后情况是 left = right + 1 最后的范围就相当于 [right+ 1, right] 这样的区间不存在，所以如果不存在的话，那么我们直接返回 -1 就可以。

int binarySearch(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;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
// 当这个小于 target 的时候
left = mid + 1;
}
}
return -1;
}


但是当我们的搜索区间是 [left，rigfht) 的时候我们最后退出的 left 是等于 right 的，所以最后我们需要判断 nums[left] == target

class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
// 注意，因为 mid 已经被搜索过了
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
// 如果索引越界，说明数组中无目标元素，返回 -1
if (left < 0 || left >= nums.length) {
return -1;
}
return nums[left] == target ? left : -1;
}
}



寻找两个数的边界


寻找左边界


两种写法

1）使用，左闭右开的形式

gift 演示：


int left_bound(int[] nums, int target) {
int left = 0, right = nums.length;
// 搜索区间为 [left, right)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 此时已经排除了这个 mid 位置的值了，因为咱们的区间是 [left, right）
right = mid;
} else if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
// 最后退出的时候是 left == right
return left;
}


后期熟练之当然可以写的更加简单，但是现阶段还是需要自己仔细写


2）使用，左闭右闭的形式

下面是进行到一个特殊的情况的时候：

这个时候我们会发现，黄色的箭头指的是 mid 的位置，这个时候我们的 left 位置在 0 ， right 的位置在 2 位置，那么下一次运行 while 里面的时候，我们的 right = mid - 1，也就是在 0 的位置，此时 mid < target 我们的 left = mid + 1；也就变成了 1 的位置，此时 right < left 也就是 left = right + 1 循环结束！！！所以最后我们判断的都是 left 因为 left 可能会越界，但是 right 就不会越界，right 是不会越过左边界的。这是因为在每一步迭代中，如果 nums[mid] > target，那么搜索区间会变成 [left, mid-1]，也就是说，right 会被更新为 mid - 1。就是在最左侧的时候我们这时候 left 都不会越过 index 是 0 的位置



找到左边的 index 需要 去靠近

gift 演示：


int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 能够找到边界的关键！
right = mid - 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
// 检查数组边界
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}



寻找右边界


也是两种写法，和上面寻找左边界一样


1）使用，左闭右开的形式

gift 演示

int right_bound(int[] nums, int target) {
int left = 0, right = nums.length;
// 范围 [)
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 能够找到边界的关键！
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
if (left == 0) return -1;
// 最后的情况应该是 left == right == 右边界的右边一个位置
return nums[left - 1] == target ? (left - 1) : -1 ;
}


2）使用，左闭右闭的形式


gift 演示


int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 能够找到边界的关键！
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
// 这⾥改为检查 right 越界的情况，⻅下图
if (right < 0 || nums[right] != target) {
return -1;
}
return right;
}



总结



最后 labuladong 推荐的是左闭右闭的形式，我也感觉这种考虑的还算是比较少的

只需要改 nums[mid] == target 条件下的情况 ，还有找哪一个返回哪一个并且判断哪一个的边界条件


int binarySearch(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;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
// 当这个小于 target 的时候
left = mid + 1;
}
}
return -1;
}


int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 能够找到边界的关键！
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
// 检查数组边界
if (right < 0 || nums[right] != target) {
return -1;
}
return right;
}


int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 能够找到边界的关键！
right = mid - 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
// 检查数组边界
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}



算法
CodeGeeX活动
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
leikooo
leikooo
等级vip
内容推荐
更多
ARTS 1025: 唯一字符与同构字符串、省词可能增加阅读负担与重新估算软件的实现成本
5
【单调栈】每日温度
3
米哈游内推～游戏AI算法实习｜强化学习方向
6
【栈模拟】字符串解码
3
【数论】求两个正整数的最大公因数与最小公倍数
3
作者分享
更多
IP 数据库体积缩小 31%，关键竟然是合并重复子树
2
提到用 Rust 重写项目，很多人的第一反应往往是性能提升。以 Bun 为例，它最初主要采用 Zig 开发，后来在 2026 年发布的 v1.4 版本中将核心代码迁移到了 Rust。用 Rust 重写，性能、安全性往往是大家想要的，但是有没有想过用 Rust 重写还能发现 bug 呢？ pgrust 这个项就是，他用 Rust 重新实现 PostgreSQL，保持通信协议和 SQL 方言兼容。为了确认新系统的行为和原版一致，开发者需要对着 PostgreSQL 的实际返回逐个比对。结果查着查着，有些异常不是新代码的锅，PostgreSQL 自己就是这样的。pgrust 开发者 Michael Malis 把其中几个报告给了 PostgreSQL 社区。 大概的问题： 1）SP-GiST 空间索引里有个函数判断点的方位，代码认为上、下、同一水平线三种情况已经穷尽了，末尾放了句「impossible case」兜底。结果在特定浮点边界附近，三种判断同时不成立，程序真走进了这个「不可能」的分支 2）日期格式缓存复用时，一个解析模式的标记没重置，导致同一条 JSONPath 查询在同一个会话里，换个执行顺序结果就不一样。 3）pgcrypto 的 crypt() 在某些输入下截断了多字节字符，返回的文本编码不合法。能存进去，但 pg_dump 导出时就炸了。 一个用 Rust 重写的新项目，测着测着，把运行了几十年的 PostgreSQL 里埋着的东西翻了出来。Rust 重写的价值，不一定只在跑得更快、更安全这一件事上。为了做到真正的兼容，开发者得把前人没怎么碰过的边界全走一遍，这个过程本身就在帮原版排雷。
4
ARTS 1025: 唯一字符与同构字符串、省词可能增加阅读负担与重新估算软件的实现成本
5
🎉 1024 程序员节快乐！ 祝编程导航里的每一位程序员：offer 多多，薪资翻倍，面试顺利，早日拿下心仪 offer！💻
17
AST：从 Java 代码理解抽象语法树
5
下载 APP