二分查找详解（while条件判断+转换值判断）

二分查找专题

前提条件：

• 有序数组
• 无重复元素

注意点：

1. 取中值mid时候，小心越界问题

int mid = (left + right) / 2;    // left+right时可能int溢出

int mid = left + ((right - left) >> 1);  //防止int溢出，同时使用位运算提高运算速度效率
1
2
3

2. 学会判断while内使用left < right还是left <= right,以及二分查找中left和right的转换值

第一种：区间左闭右闭类型[left,right]

​ while判断条件为while(left <= right) 使用<=,因为right是可以取到的

​ 同时while内的转换使用的是 left = mid + 1 或 right = mid - 1;

	public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target) {
                //因为nums[mid]不满足条件，并且区间左闭，left可以取到，所以应取left = mid+1,让区间无mid
                left = mid + 1;
            }else if(nums[mid] > target) {
                //因为nums[mid]不满足条件，并且区间右闭，right可以取到，所以应取right = mid-1,让区间无mid
                right = mid - 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

第二种：区间左闭右开类型[left,right)

​ while判断条件为while(left < right) 使用<,因为right区间无法取到

​ 同时while内的转换使用的是 left = mid + 1 或 right = mid

public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target) {
                //因为nums[mid]不满足条件，并且区间左闭，left可以取到，所以应取left = mid+1,让区间无mid
                left = mid + 1;
            }else if(nums[mid] > target) {
                //因为nums[mid]不满足条件，并且区间右开，right不会取到，所以取right = mid就可以让区间无mid
                right = mid;
            }else{
                return mid;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

​ 举一个例子，在一个有序不重复数组中进行二分查找，当right=nums.length-1时，属于左闭右闭，选用第一种，当right=nums.length时，属于左闭右开，选用第二种。

​ 根据具体的应用场景进行具体的修改，重在理解二分过程和边界。

第三种：数组有序，但包含重复元素，寻找重复元素的区间

有重复元素会导致返回的元素不唯一，例如力扣34在排序数组中查找元素的第一个和最后一个位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums == null || nums.length == 0)
            return new int[]{-1,-1};
        //1.寻找右边界，有与target相同的值的时候优先右偏
        //最终的结果left返回的一定是第一个比target大的值的位置，所以它为右边界
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] <= target) {
                left = mid + 1;
            }else if(nums[mid] > target) {
                right = mid - 1;
            }
        }
        int right_bound = left;
        
        //2.寻找左边界，有与target相同的值的时候优先左偏
        //最终的结果right返回的一定是第一个比target小的值的位置，所以它为左边界
        left = 0;
        right = nums.length - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target) {
                left = mid + 1;
            }else if(nums[mid] >= target) {
                right = mid - 1;
            }
        }
        int left_bound = right;
        
        //3.判断是否存在target值区间
        if(right_bound - left_bound - 1 < 1){
            return new int[]{-1,-1};
        }else{
            return new int[]{left_bound+1,right_bound-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

例题：

力扣704. 二分查找

力扣69. x 的平方根

力扣34. 在排序数组中查找元素的第一个和最后一个位置