二分查找算法

二分查找框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[] nums,int target){
    int left =0,right =...;
    while(...){
        int mid = left+(right-left) / 2;
        if(nums[mid] == target){
            ...
        }else if(nums[min] < target){
            ...
        }else if(nums[min] > targetn){
            ...
        }
    }
    return ...;
}

注意：
代码中 left+(right - left) / 2 和 (left+right) / 2 的结果相同，防止 left 和 right 太大，导致益处问题。

基本的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[] nums,int target){
    int left = 0,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;
}

  • 为什么 while 循环的条件的 <=,而不是 < ?
    因为初始化 right = nums.length -1,而不是 nums.lenght

  • while(left<= right) 的终止条件是 left = right+1 , 区间形式 [right+1,right]

  • while(left < right) 的终止条件是 left == right , 区间形式 [right,right]

注意： 使用while(left < right),返沪值要特殊处理

1
2
3
4
while(...){
    ...
}
return nums[left] == target ? left : -1;

  • 为什么 left = mid + 1 , right = mid - 1 .有的是 right = mid ,left = mid ?
    因为 「搜索区间」 的不同，导致要计算的边界也不相同。

寻找左侧边界的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int left_bound(int[] nums,int target){
    int left = 0, 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;
}

  • ** 为什么 while 中的是 < 而不是 <= ?**

    因为 right = nums.length 而不是 nums.length - 1
    while(left < right) 终止的条件是 left == right

  • 为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办 ?

    在返回的时候额外判断一下 nums[left] 是否等于 target

    1
    2
    3
    4
    5
    6
    7
    8
    9
    while(left < right){
        ...
    }
    // 此时，target 比所有数都大，返回 -1
    if(left == nums.length){
        return -1;
    }
    //判断 nums[left] 是不是 target
    return nums[left] == target ? left : -1;

为什么该算法能够搜索左侧边界 ?

关键在于对于 nums[mid] == target 这种情况的处理：

1
2
if (nums[mid] == target)
   right = mid;

  • 为什么返回 left 而不是 right ?
    都是一样的，因为 while 终止的条件是 left == right。

  • 把 right 变成 nums.length - 1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    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){
                right = mid - 1; // 收缩右侧边界
            }else if(nums[mid] < target){ // 搜索区间变为 [mid+1, right]
                left = mid + 1;
            }else if(nums[mid] > target){ // 搜索区间变为 [left, mid-1]
                right = mid - 1; //注意
            }
        }
        if( left == nums.length){
            return -1;
        }
        
        return nums[left] == target ? left : -1;
    }

寻找右侧边界的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int left_bound(int[] nums,int target){
    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
if (nums[mid] == target) {
  left = mid + 1;

当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的左边界 left，使得区间不断向右靠拢，达到锁定右侧边界的目的。

  • 为什么返回 left - 1 而不是 right
    首先，while 循环的终止条件是 left == right，所以 left 和 right 是一样的，非要体现右侧的特点，返回 right - 1 。

  • 返回 -1 的操作,如果 nums 中不存在 target

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    while(left < right){
      ...
    }
    //判断target 是否存在于nums中
    //此时 left-1 索引越界
    if(left - 1 < 0){
      return -1;
    }
    // 判断 nums[left-1] 是不是target
    return nums[left-1] == target ? (left - 1) : -1;

  • 把 right 变成 nums.length - 1

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1; //注意
            }
        }
         // 最后改成返回 left - 1
        if (left - 1 < 0) return -1;
        return nums[left - 1] == target ? (left - 1) : -1;
    }

逻辑统一

  • 第一个，最基本的二分查找算法

    因为我们初始化 right = nums.length - 1
    所以决定了我们的「搜索区间」是 [left, right]
    所以决定了 while (left <= right)
    同时也决定了 left = mid+1 和 right = mid-1
    因为我们只需找到一个 target 的索引即可
    所以当 nums[mid] == target 时可以立即返回

  • 第二个，寻找左侧边界的二分查找

    因为我们初始化 right = nums.length
    所以决定了我们的「搜索区间」是 [left, right)
    所以决定了 while (left < right)
    同时也决定了 left = mid + 1 和 right = mid

    因为我们需找到 target 的最左侧索引
    所以当 nums[mid] == target 时不要立即返回
    而要收紧右侧边界以锁定左侧边界

  • 第三个，寻找右侧边界的二分查找

    因为我们初始化 right = nums.length
    所以决定了我们的「搜索区间」是 [left, right)
    所以决定了 while (left < right)
    同时也决定了 left = mid + 1 和 right = mid

    因为我们需找到 target 的最右侧索引
    所以当 nums[mid] == target 时不要立即返回
    而要收紧左侧边界以锁定右侧边界

    又因为收紧左侧边界时必须 left = mid + 1
    所以最后无论返回 left还是 right，必须减一

  • 第四个，统一成了两端都闭

    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
    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;
            }
        }
        // 判断 target 是否存在于 nums 中
        // 此时 target 比所有数都大，返回 -1
        if (left == nums.length) return -1;
        // 判断一下 nums[left] 是不是 target
        return nums[left] == target ? left : -1;
    }
        
    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;
            }
        }
        // 此时 left - 1 索引越界
        if (left - 1 < 0) return -1;
        // 判断一下 nums[left] 是不是 target
        return nums[left - 1] == target ? (left - 1) : -1;
    }