二分法是典型的分治法应用
二分查找
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 27 28 29 30 31 32 33
| int binarySearch(int[] nums, int target) { int left = 0, right = ...;
while(...) { int mid = left + (right - left) / 2; if (nums[mid] == target) { ... } else if (nums[mid] < target) { left = ... } else if (nums[mid] > target) { right = ... } } return ...; }
int binarySearch(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; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid - 1; } return -1; }
|
left < right
or left <= right
right = length-1
,右边能取到,所以left<=right
while(left <= right)
的终止条件是 left == right + 1
,写成区间的形式就是 [right + 1, right]
,或者带个具体的数字进去 [3, 2],可见这时候区间为空,因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的,直接返回 -1 即可。
while(left < right)
的终止条件是 left == right
,写成区间的形式就是 [right, right]
,或者带个具体的数字进去 [2, 2],这时候区间非空,还有一个数 2,但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了,索引 2 没有被搜索,如果这时候直接返回 -1 就是错误的。
left, right = mid + 1, mid - 1
or left, right = mid, mid
看后续的搜索区间,能不能排除mid,然后看之前right的取值,后续是需要[left, right]还是[left, right)
左侧边界
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| int left_bound(int[] nums, int target) { if (nums.length == 0) return -1; int left = 0; int right = nums.length; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] == target) { right = mid; } else if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } return left; }
|
能去左侧边界主要的原因是在nums[mid] == target
的时候,right=mid
右侧边界
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| int right_bound(int[] nums, int target) { if (nums.length == 0) return -1; 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) { left = mid + 1; } else if (nums[mid] > target) { right = mid; } } return left - 1; }
|
为啥能找到右边界
1 2 3
| if (nums[mid] == target) { left = mid + 1; }
|
为啥返回left - 1
结束时 left = right, 所以 right - 1 也行
为啥要-1, 因为为找到右边界,left = mid + 1 了,此时的left不一定等于target
right = length - 1
以上3种都可以写成right = length - 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 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| int binary_search(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) { return mid; } } return -1; }
int left_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) { 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; } } if (right < 0 || nums[right] != target) { return -1; } return right; }
|
实战
横竖有序,从右上角开始,大于target向左移,小于targte向下移
考虑2分法
旋转排序数组
合并区间