二分法（含 gift 演示）
leikooo
2024-02-20 16:46
阅读1952
二分法
二分法原理很简单，但是细节是魔鬼
寻找一个数
当我们使用 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;
}
评论
问答助学
相关内容
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
作者分享
ARTS 0815: 分隔链表、大删除是加活不是减负与协议栈如何一层层拆信封
4
DeepSeek Harness 缓存命中率太惊人了，有时候竟然能到 99%，看鱼皮哥的视频竟然还出现过 100% 😱 https://www.bilibili.com/video/BV1VkgK6NEZS
7
ARTS 0809: 反转链表、Shopify 如何用 MySQL 解决超卖与 AI 时代程序员的价值
5
译文：《SwiftUI 七年：平庸的故事》
SwiftUI 在 2019 年高调发布，本应成为苹果全平台成熟、可量产的 UI 未来。七年过去，到了 2026 年，它仍像一场永不结束的 beta：布局难预期、性能不稳、数据流混乱，还几乎没有可靠的向后兼容，开发者被迫写一堆 shim 和 workaround。
作者用苹果官方教程（甚至是有问题的）以及与 UIKit 的对比说明：SwiftUI 用“看起来方便”换掉了精确的工程控制。更深一层，他认为这反映了苹果从 Cocoa、Aqua、Auto Layout 那种不妥协的工艺，转向“够用就行”的企业文化。
SwiftUI 为何存在
苹果并非单纯想提供更好工具，而是不得不应对竞争：React、React Native、Flutter 让“一套代码多端跑”变得诱人；Mac 上原生应用又日渐被网页和 Electron 吃掉。SwiftUI 要同时拴住原生生态、并降低移植到 Mac 的成本。卖点是：响应式数据流、声明式布局、跨平台复用。
数据流
“单一数据源”听起来很美，实际却是 @State、@Binding、ObservedObject，再到 Observation / @Observable 的不断换代。你很难确定视图会更新几次、为何更新；它该忽略的变化会反应，该关心的变化又可能忽略 - - 像个黑盒。
布局系统
基于尺寸协商的布局在 Keynote 里很合理，做浮动视图、自定义侧边栏时却极度不稳定。官方教程里一个很普通的侧边栏，多年仍有问题。布局脆弱到最后往往只能上 GeometryReader - - 一旦用了，声明式优势就没了，还要手算坐标，而且下一版布局规则一变，数学还得重写。
API 稳定与功能对等
代码里满是 if #available。滚动收起键盘要到 iOS 16；工具栏定制很晚才来；网络图片 AsyncImage 要到 iOS 15，缓存相关 API 到 2026 年 7 月仍在 beta。旧 API 常被换掉（如 NavigationView → NavigationStack），开发者要维护多套实现，等于替苹果做 QA。对比 Android 的 Jetpack Compose 可作为依赖打包回退到旧设备，SwiftUI 做不到“写最新 API、稳定回退”。
性能
在真实对比里，即便做了后台解码等优化，SwiftUI 图片网格滚动仍明显不如 UIKit。若展示一堆 JPEG 都得靠顶级芯片撑，架构本身就有问题。
跨平台神话
苹果说的是“学一次、到处用”，不是“写一次、到处跑”。iOS 上学到的布局很少直接适用 Mac；同一套 view 跨平台实现也不一致。结果常变成：学一次、再学一次、某处能用、处处要调。
哲学转向
最大的问题是“够用就行”：覆盖 90% 用例就算成功，用 velocity 掩盖质量下降。作者列举系统与一线应用中的各种瑕疵，认为这不是偶然，而是苹果主动降低质量门槛 - - 所以即使过了七年，他仍不信任 SwiftUI。
结论
对构建稳定、高性能、可维护系统真正重要的部分，SwiftUI 几乎都有问题。它不是“极差”，而是平庸 - - 用假便利换真精度，要么你花时间给框架打补丁，要么把半成品发出去。作者更宁愿继续用“遗留”的 UIKit / AppKit。
最后小总结：
最让人不能接受的不是“SwiftUI 还有 bug”，而是它把“看起来很快”当成了工程上的完成态。声明式、预览、跨平台，每一项都在秀高级感，可真正写进业务后，你面对的是难预测的重绘、脆弱的布局、层层 #available，以及把兼容和排错外包给业务方的现实。七年够长了，若还靠“框架还年轻”解释，那更像是对标准的侮辱。技术选型从来不只是语法偏好，而是你选的是可预期性、可维护成本，以及对用户体验的态度。平庸的“成功”往往比明显失败更危险 ，你说它能上线、能 demo、能交差，但是却在细节里一点点磨损信任。工具可以换代，但对质量的要求不该跟着一起降级。
4
ARTS 0802: 合并有序链表、AI 时代的技术断层与 TCP 200ms 延迟之谜
5
