本文取自labuladong的算法小抄，并对while结束后的left和right位置做了补充说明，大佬太强了
https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/er-fen-cha-zhao-xiang-jie
所有模板统一采用开区间[left, right]做法
1. 二分查找模板
找到返回下标，找不到返回-1
1
2
3
4
5
6
7
8
9
10
11
12
| public int binarySearch(int[] nums, int target){
int left = 0, right = nums.length - 1, mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (target == nums[mid]) return mid;
else if (target < nums[mid]) right = mid - 1;
else if (target > nums[mid]) left = mid + 1;
}
return -1;
}
|
力扣704
https://leetcode-cn.com/problems/binary-search/
2. 二分查找最左侧
[1,2,2,2,2,3]找最左边的2，也就是下标返回1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int binarySearchLeft(int[] nums, int target){
int left = 0, right = nums.length, mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (target == nums[mid]) right = mid - 1;
else if (target < nums[mid]) right = mid - 1;
else if (target > nums[mid]) left = mid + 1;
}
if (left >= nums.length || target != nums[left]) return -1;
return left;
}
|
3. 二分查找最右侧
[1,2,2,2,2,3]找最右边的2，也就是下标返回4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| public int binarySearchRight(int[] nums, int target){
int left = 0, right = nums.length, mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (target == nums[mid]) left = mid + 1;
else if (target < nums[mid]) right = mid - 1;
else if (target > nums[mid]) left = mid + 1;
}
if (right < 0 || target != nums[right]) return -1;
return right;
}
|
力扣34
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
4. 循环结束时的left和right
如果找不到target，则程序会走到while循环结束后面的语句，此时right会比left小1，left为数字本应该在的位置，因此只需要返回left即可
如：[1,3,5,6] target=2，找不到，则while结束后left=1, right=0
力扣35
https://leetcode-cn.com/problems/search-insert-position/
1
2
3
4
5
6
7
8
9
10
| public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1, mid = 0;
while(left <= right){
mid = left + (right - left) / 2;
if(target == nums[mid]) return mid;
else if(target < nums[mid]) right = mid - 1;
else if(target > nums[mid]) left = mid + 1;
}
return left;
}
|
其他动态规划的题目可以点击这里
