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

二分法（含 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
内容推荐
更多
最近刷算法的一些心得~
6
Claude Code 源码架构深度解析：1884 个文件背后的 AI 编程工具设计哲学
23
深度解析 Claude Code 记忆系统：从源码看 AI 编程助手如何"记住"你的项目
6
LeetCode Hot 100 二分查找篇 - 每次砍一半，六道题从入门到穿透
2
卷AI、卷算法、2026 年的前端工程师到底在卷什么？
7
作者分享
更多
Spring 团队开发者布道师 Josh Long，从 2011 年起每周二坚持写 This Week in Spring https://spring.io/authors/joshlong，大概 15 年半从未间断，到现在大概写了 800 期以上😱 大佬在采访里他说，写博客不是额外负担，而是逼自己整理每周所学的「强制机制」——反正本来就会刷社区动态，写出来既方便自己，也帮到别人。更重要的是 Spring 一直在变：微服务、AI……永远有新东西可聊，停一周就容易掉队。一旦养成习惯，坚持往往比重新开始更容易。 这种级别的大佬都还在用周更逼自己不掉队，我更没理由再拖了。还有之前左耳朵耗子大佬说的 ARTS 打卡，我老实说只撑了两周，真的需要捡起来了，加油✊
10
试了下 Grok CLI：curl -fsSL https://x.ai/cli/install.sh | bash 虽然功能不如 Claude Code 全，但能免费用 Grok 4.5 啊😍。一行 prompt 大概 3 分钟就生成出来了而且没有报错：" Three.js UMD 构建。正在实现完整的太阳系模拟（含自定义轨道控制，兼容本地打)"。 大伙可以访问试试：https://solar-system-seven-mocha.vercel.app/
4
彻底搞懂 Spring AI Tool Calling：从底层协议到源码执行全流程
7
别用 JWT 管理用户会话
9
没想到 Bot 占全球 HTML 流量的 50% 以上了，被这个比例给震惊到了。还有开发者在评论区说自己的网站「每天」访问量 250k 但是 Cloudflare 显示真实的用户只有 150 个😱 数据来源：https://radar.cloudflare.com/traffic#bot-vs-human
5
下载 APP