前提考虑(一些特点???):
- 有序数组
- 不重复元素(唯一下标)
- 所谓闭区间就是left或者right的初始值是等于初始值或者最后一个元素的索引。
双闭区间`
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;//没找到
}
- 终止条件:找到了
- if(nums[mid] == target)
return mid;
- 没找到:区间为空–left==right+1,所以while(left <= right) (while(left < right) 的终止条件是 left == right,这个区间不是空的,那个数字就会漏掉)
- 移动的时候target本身就已经判断过了,所以要mid+1或者-1
找边界
4、为什么该算法能够搜索左侧边界?
答:关键在于对于 nums[mid] == target 这种情况的处理:
if (nums[mid] == target)
right = mid;
可见,找到 target 时不要立即返回,而是缩小「搜索区间」的上界 right,在区间 [left, mid) 中继续搜索,即不断向左收缩,达到锁定左侧边界的目的。
常用代码:左闭右开
我觉得就这些了,让我明天实践一下,呜呼
作者:labuladong
链接:https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。