| 失效链接处理 |
|
labuladong的刷题笔记V1.7(力扣版) PDF 下载
本站整理下载：
相关截图：
主要内容：
基本思路
PS：这道题在《算法⼩抄》 的第 71 ⻚。
⼆分搜索的难点就在于如何搜索左侧边界和右侧边界，代码的边界的控制⾮常考验你的微操，这也是很多⼈
知道⼆分搜索原理但是很难写对代码的原因。
⼆分搜索框架详解 专⻔花了很⼤篇幅讨论如何写对⼆分搜索算法，总结来说：
写对⼆分搜索的关键在于搞清楚搜索边界，到底是开区间还是闭区间？到底应该往左侧收敛还是应该往右侧
收敛？
深⼊的探讨请看详细题解。
详细题解：我作了⾸诗，保你闭着眼睛也能写对⼆分查找
解法代码
class Solution {
public int[] searchRange(int[] nums, int target) {
return new int[]{left_bound(nums, target), right_bound(nums,
target)};
}
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
在线⽹站 labuladong的刷题三件套
12 / 498
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 检查出界情况
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
int right_bound(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 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;
}
}
类似题⽬：
704. ⼆分查找（简单）
在线⽹站 labuladong的刷题三件套
13 / 498
704. ⼆分查找
Stars 103k
知乎 @labuladong
公众号 @labuladong
B站 @labuladong
标签：⼆分搜索
给定有 n 个元素的升序整型数组 nums 和⼀个⽬标值 target，写⼀个函数搜索 nums 中的 target，如果⽬
标值存在返回下标，否则返回 -1。
示例 1:
输⼊：nums = [-1,0,3,5,9,12], target = 9
输出：4
解释：9 出现在 nums 中并且下标为 4
示例 2:
输⼊：nums = [-1,0,3,5,9,12], target = 2
输出：-1
解释：2 不存在 nums 中因此返回 -1
基本思路
PS：这道题在《算法⼩抄》 的第 71 ⻚。
⼆分搜索的基本形式，不过并不实⽤，⽐如 target 重复出现多次，本算法得出的索引位置是不确定的。
更常⻅的⼆分搜索形式是搜索左侧边界和右侧边界，即对于 target 重复出现多次的情景，计算 target 的
最⼩索引和最⼤索引。
这⼏种⼆分搜索的形式的详细探讨⻅详细题解。
详细题解：我作了⾸诗，保你闭着眼睛也能写对⼆分查找
解法代码
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target)
return mid;
在线⽹站 labuladong的刷题三件套
14 / 498
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
}
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
