# 4. 例题讲解：「力扣」第 35 题：搜索插入位置
思路分析：
根据示例 3：
输入: [1, 3, 5, 6], 7
输出: 4
1
2
2
如果目标元素大于输入数组中的最后一个元素，返回数组的最后一个元素的下标 + 1。
根据示例 2：
输入: [1,3,5,6], 2
输出: 1
1
2
2
需要返回第 1 个 大于等于（等于的情况可以看示例 1，这里省略） 目标元素 2 的下标，因此输出 1。因此 如果当前 mid 看到的数值严格小于 target，那么 mid 以及 mid 左边的所有元素就一定不是题目要求的输出，就根据这一点可以写出本题二分查找算法的完整逻辑。
参考代码 2：（第 35 题代码）
public class Solution {
public int searchInsert(int[] nums, int target) {
int len = nums.length;
// 特殊判断
if (nums[len - 1] < target) {
return len;
}
// 程序走到这里一定有 target <= nums[len - 1]
int left = 0;
int right = len - 1;
// 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target){
// 下一轮搜索的区间是 [mid + 1..right]
left = mid + 1;
} else {
// 下一轮搜索的区间是 [left..mid]
right = mid;
}
}
return left;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
值得一提的是：由于执行到最后 nums[left..right] 里一定存在插入元素的位置，并且退出循环的时候一定有 left == right 成立，因此直接返回 left 或者 right 均可。
这样的思路还可以完成第 704 题。
参考代码 3：（第 704 题代码）
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int left = 0;
int right = len - 1;
// 在 nums[left..right] 里查找 target
while (left < right) {
// 为了防止 left + right 整形溢出，写成这样
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 下一轮搜索区间：[mid + 1..right]
left = mid + 1;
} else {
// 下一轮搜索区间：[left..mid]
right = mid;
}
}
if (nums[left] == target){
return left;
}
return -1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
int left = 0;
int right = len - 1;
// 在 nums[left..right] 里查找 target
while (left < right) {
// 为了防止 left + right 整形溢出，写成这样
int mid = left + (right - left + 1) / 2;
if (nums[mid] > target) {
// 下一轮搜索区间：[left..mid - 1]
right = mid - 1;
} else {
// 下一轮搜索区间：[mid..right]
left = mid;
}
}
if (nums[left] == target){
return left;
}
return -1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
- 退出循环的时候，我们不能确定
nums[left]是否等于target，因此还需要单独做一次判断； - 「选项卡二」我们还给出了一版代码，具体细节大家可以在阅读完本题解以后再来理解它。