二分法初学

前提考虑(一些特点???):

  • 有序数组
  • 不重复元素(唯一下标)
  • 所谓闭区间就是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)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

上一篇:矩阵中最大的矩形


下一篇:215. Kth Largest Element in an Array