leetcode之二分查找问题

发表于 | 分类于
  • 单调性问题
  • 存在着两段性的性质，即一半满足某一个性质，另一半不满足某个性质。

均可以使用二分查找。

1575181703866

红色表示满足某一个性质，绿色表示不满足某一个性质。

模板一

求红色的右边界情况。

if mid in 红 [L,R]->[M,R] L=M

else mid in 绿 [L,R]->[L,M-1] R=M-1

注意，mid应该是取(L+R)/2+1，防止死循环

1
2
3
4
5
6
7
8
9
while(l<r){
    int mid = start+(end-start+1)/2;
    if(check(mid)){
        l = mid;
    }else{
        r = mid-1;
    }
    return l;
}

模板二

求绿色的左边界情况

if mid in 绿 [L,R]->[L,M] R=M

else mid in 红 [L,R]->[M+1,R] L=M+1

mid取值是(L+R)/2

1
2
3
4
5
6
7
8
9
while(l<r){
    int mid = l+(r-l)/2;
    if(check(mid)){
        r = mid;
    }else{
        l = mid+1;
    }
    return l;
}

二分流程

确定二分边界：left = 0,right=x

编写二分代码框架

设定一个性质

判断区间如何更新

如果更新方式是l=mid,r=mid-1，那么mid上取整

69.求开方

按照框架来做：

设定一个性质：t*t<=x

区间如何更新：满足区间的右边界点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//check:mid*mid<=target 取左侧边界 
public int mySqrt(int x) {
    if(x<=1){
        return x;
    }
    int left = 1;
    int right = x;
    while(left<right){
        int mid = left+(right-left+1)/2;
        //防止溢出
        if(mid<=x/mid){
            left = mid;
        }else{
            right = mid-1;
        }
    }
    return left;
}

35.搜索插入位置？

边界判断

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int searchInsert(int[] nums, int target) {
    if(nums[nums.length-1]<target){
        return nums.length;
    }
    //设定一个性质，t>=target，所以取右侧的左边界点
    int l = 0;
    int r = nums.length-1;
    while(l<r){
        int mid = l+(r-l)/2;
        if(nums[mid]>=target){
            r= mid;
        }else{
            l = mid+1;
        }
    }
    return l;
}

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置.

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
public int[] searchRange(int[] nums, int target) {
    if(nums.length==0){
        return new int[]{-1,-1};
    }
    int[] res = new int[2];
    //寻找左边界，check:nums[mid]<target  右侧的边界点作为结果
    int l= 0;
    int r= nums.length-1;
    while (l<r){
        int mid = l+(r-l)/2;
        if(nums[mid]<target){
            l = mid+1;
        }else{
            r = mid;
        }
    }
    if(nums[left]!=target){
        return new int[]{-1,-1};
    }else{
        res[0] = left;
    }

    //寻找右边界.check:nums[mid]<=target, 左侧的边界点作为结果
    l = 0;
    r = nums.length-1;
    while(l<r){
        int mid = l+(r-l+1)/2;
        if(nums[mid]<=target){
            l = mid;
        }else{
            r = mid-1;
        }
    }
    res[1] = left;
    return res;
}

74.搜索二维矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//check:nums[mid]<=target 左侧边界值
public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix.length==0||matrix[0].length==0){
        return false;
    }
    int l = 0;
    int m = matrix.length;
    int n = matrix[0].length;
    int r = m*n-1;
    while(l<r){
        int mid = l+(r-l+1)/2;
        int first_dim = mid/n;
        int second_dim = mid%n;
        if(matrix[first_dim][second_dim]<=target){
            l = mid;
        }else{
            r = mid-1;
        }
    }
    return matrix[l/n][l%n]==target;
}

162.寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
     * 寻找峰值元素，当nums[mid]<nums[mid+1]时，表明mid右侧是有增加的，因为nums[n] = -∞，
     * 所以mid右侧必定会有一个峰值点
     * */
public int findPeakElement(int[] nums) {
    int left = 0;
    int right = nums.length-1;
    while(left<right){
        int mid = left+(right-left)/2;
        if(nums[mid]<=nums[mid+1]){
            left = mid+1;
        }else{
            right = mid;
        }
    }
    return left;
}

基本的二分查找

搜索一个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int binarySearch(int [] arr,int val){
    int start = 0;
    int end = arr.length-1;
    while(start<=end){//
        int mid = start+(end-start)/2;
        if(arr[mid]>val){
            end = mid-1;//
        }else if(arr[mid]<val){
            start = end+1;//
        }else{
            return mid;
        }
    }
    return -1;
}

744.寻找比目标字母大的最小字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//check:letters[mid]<=target 右侧边界
public char nextGreatestLetter(char[] letters, char target) {
    if(target>=letters[letters.length-1]){
        return letters[0];
    }
    int start = 0;
    int end = letters.length-1;
    while (start<end){
        int mid = start+(end-start)/2;
        if(letters[mid]<=target){
            start = mid+1;
        }else{
            end = mid;
        }
    }
    return letters[start];
}

540.有序数组的 Single Element

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
/**
 * 给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数
 * */
public int singleNonDuplicate(int[] nums) {
    //当数组长度为1的时候
    if(nums.length==1){
        return nums[0];
    }
    //当单一元素在第一个位置或者在最后一个位置
    if(nums[0]!=nums[1]){
        return nums[0];
    }
    if(nums[nums.length-1]!=nums[nums.length-2]){
        return nums[nums.length-1];
    }

    int start = 0;
    int end = nums.length-1;
    while(start<end){
        int mid = start+(end - start)/2;
        if((nums[mid]!=nums[mid-1])&&(nums[mid]!=nums[mid+1])){
            return nums[mid];
        }
        /**mid为偶数，前面必定是偶数，因此，当nums[mid] == nums[mid-1]， （奇数个） 3 3，因此，单个元素必定在前半段
             * 当nums[mid] != nums[mid-1]， （奇数个）2 3，因此，单个元素必定在后半段
             * mid
             * **/
        if (mid % 2 == 0) {
            if(nums[mid] == nums[mid-1]) {
                end = mid -1;
            }else{
                start = mid;
            }
        }
        /**mid 为奇数，前面必定为奇数，因此，当nums[mid] == nums[mid-1]， （偶数个） 3 3，因此，单个元素必定在后半段
             * 当nums[mid] != nums[mid-1]， （偶数个）2 3，因此，单个元素必定在前
             *
             * */
        if (mid % 2 == 1) {
            if(nums[mid] == nums[mid-1]) {
                start = mid;
            }else{
                end = mid-1;
            }
        }
    }
    return 0;
}

153.旋转数组的最小数字?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 * ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
 * 请找出其中最小的元素。
 * */
public int findMin(int[] nums) {
    //假如nums[mid]>最后一个元素，那么必定在[mid+1,r]之间
    int l = 0;
    int r = nums.length-1;
    while (l<r){
        int mid = l+(r-l)/2;
        if(nums[mid]>nums[r]){
            l = mid+1;
        }else{
            r = mid;
        }
    }
    return nums[l];
}