二分边界问题

# 整形溢出

int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;
System.out.println((a + b) / 2);         // 错误，整形溢出
System.out.println(a + (a - b) >> 1);    // 错误，位运算优先级最低
System.out.println(a + (a - b) / 2);     // 正确
System.out.println((a + b) >>> 1);       // 正确，>>> 就算溢出也能得到正确答案

1
2
3
4
5
6

# 循环不变量

# 26. 删除有序数组中的重复项 (opens new window)

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if(n<2) return n;
        // 循环不变量：nums[0...j)无重复元素
        // i指向遍历的元素，j指向下一个要赋值的元素
        int j=1;
        for(int i=1;i<n;i++){
            if(nums[i]!=nums[j-1]){
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}

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

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if(n<2) return n;
        // 循环不变量：nums[0...j]无重复元素
        // j是刚赋值完的元素的下标
        int j=0; 
        for(int i=1;i<n;i++){
            if(nums[i]!=nums[j]){
                j++;
                nums[j] = nums[i];
            }
        }
        return j+1;
    }
}

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

# 27. 移除元素 (opens new window)

class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        if(n==0) return 0;
        // 循环不变量：nums[0...j) 不包含val，j指向要赋值元素的位置
        int j=0;
        for(int i=0;i<n;i++){
            if(nums[i]!=val){
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        if(n==0) return 0;
        // 循环不变量：nums[0...j] 不包含val，j指向刚赋值完元素的位置
        int j=-1;
        for(int i=0;i<n;i++){
            if(nums[i]!=val){
                j++;
                nums[j] = nums[i];
            }
        }
        return j+1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 283. 移动零 (opens new window)

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        if(n<2) return ;
        // 循环不变量：nums[0...j]!=0
        // nums[j...i]==0
        int j=0; // j 指向下一个非零元素的位置
        for(int i=0;i<n;i++){
            if(nums[i]!=0){
                nums[j] = nums[i];
                j++;
            }
        }
        for(int i=j;i<n;i++){
            nums[i] = 0;
        }
    }
}

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

class Solution {
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        if(n<2) return ;
        int j=-1; // j 指向马上要赋值的元素
        for(int i=0;i<n;i++){
            if(nums[i]!=0){
                j++;
                nums[j] = nums[i];
            }
        }
        for(int i=j+1;i<n;i++){
            nums[i] = 0;
        }
    }
}

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

# 80. 删除有序数组中的重复项 II (opens new window)

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if(n<3) return n;
        // 循环不变量：nums[0...j)最终返回数组
        // j指向下一个要填写的元素
        // [0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4]
        //           j
        //              i
        int j=2;
        for(int i=2;i<n;i++){
            if(nums[i]!=nums[j-2]){
                nums[j] = nums[i];
                j++;
            }
        }
        return j;
    }
}

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

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if(n<3) return n;
        // 循环不变量：nums[0...j]最终返回数组
        // j指向已经赋值的最后一个元素
        int j=1;
        for(int i=2;i<n;i++){
            if(nums[i]!=nums[j-1]){
                j++;
                nums[j] = nums[i];
            }
        }
        return j+1;
    }
}

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

# 红蓝标记法

红蓝标记法：<target为红色，>=target为蓝色

左闭右闭

条件：while(l<=r)

倒数第二步：l,mid,r都指向 target；

最后一步：r=mid-1，l-1都为小于target（红色），r+1都为大于等于target（蓝色），根据循环不变量 r+1即为答案（也可以是 l）；

int left_bound(int[] nums,int target){
    int l=0,r=nums.length-1;
    //区间不为空
    while(l<=r){
        int mid = l+(r-l)/2;
        if(nums[mid]<target){
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    return l;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

左闭右开

条件：while(l<r)

循环到 l,mid,r都指向target，区间为空，循环就结束了，返回 l,r都可以；

int left_bound2(int[] nums,int target){
    int l=0,r=nums.length;
    //区间不为空
    while(l<r){
        int mid = l+(r-l)/2;
        if(nums[mid]<target){
            l = mid+1;
        }else{
            r = mid;
        }
    }
    return l;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

左开右开

条件：while(l+1<r)

循环到 r指向target,l指向<target的值时区间为空，退出循环，返回 r；

int left_bound3(int[] nums,int target){
    int l=-1,r=nums.length;
    //区间不为空
    while(l+1<r){
        int mid = l+(r-l)/2;
        if(nums[mid]<target){
            l = mid;
        }else{
            r = mid;
        }
    }
    return r;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 704. 二分查找 (opens new window)

class Solution {
    public int search(int[] nums, int target) {
        int l=0,r=nums.length-1;
        while(l <= r) {
            int mid = (l+r)>>>1;
            if(nums[mid]>target)
                r = mid-1;
            else if(nums[mid]<target)
                l = mid+1;
            else   
                return mid;
        }
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 153. 寻找旋转排序数组中的最小值 (opens new window)

class Solution {
    public int findMin(int[] nums) {
        int l=0,r=nums.length-2;
        int target = nums[nums.length-1];
        while(l<=r){
            int mid = (l+r)>>>1;
            if(nums[mid]<target)
                r = mid-1;
            else
                l = mid+1;
        }
        return nums[l];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 162. 寻找峰值 (opens new window)

class Solution {
    public int findPeakElement(int[] nums) {
        int l=0,r=nums.length-2;
        while(l<=r){
            int mid = (l+r)>>>1;
            if(nums[mid]>nums[mid+1])
                r = mid-1;
            else
                l = mid+1;
        }
        return l;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 33. 搜索旋转排序数组 (opens new window)

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int i = findMin(nums);
        if(target>nums[n-1]){
            return bound(nums,0,i-1,target);
        }
        return bound(nums,i,n-1,target);
    }
    // 寻找最小值索引
    int findMin(int[] nums){
        int l=0,r=nums.length-2;
        int target = nums[nums.length-1];
        while(l<=r){
            int mid = (l+r)>>>1;
            if(nums[mid]<target){
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
    // 寻找target的左边界
    int bound(int[] nums,int l,int r,int target){
        while(l<=r){
            int mid = (l+r)>>>1;
            if(nums[mid]<target){
                l = mid+1;        
            }else{
                r = mid-1;
            }
        }
        return nums[l]==target?l:-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

# 34. 在排序数组中查找元素的第一个和最后一个位置 (opens new window)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = bound(nums,target);
        if(l==nums.length || nums[l]!=target){
            return new int[]{-1,-1};
        }
        int r = bound(nums,target+1)-1;
        return new int[]{l,r};
    }
    int bound(int[] nums,int target){
        int l=0,r=nums.length-1;
        while(l<=r){
            int mid = (l+r)>>>1;
            if(nums[mid]<target){
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        return l;
    }
}

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

# 35. 搜索插入位置 (opens new window)

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l=0,r=nums.length-1;
        while(l<=r){
            int mid = (l+r)>>>1;
            if(target>nums[mid])
                l = mid+1;
            else 
                r = mid-1;
        }
        return r+1;
        
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 74. 搜索二维矩阵 (opens new window)

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int l=0,r=m*n-1;
        while(l<=r){
            int mid = (l+r)>>>1;
            if(f(matrix,mid)<target)
                l = mid+1;
            else if(f(matrix,mid)>target)
                r = mid-1;
            else 
                return true;
        }
        return false;
    }
    int f(int[][] matrix,int k){
        int m = matrix.length;
        int n = matrix[0].length;
        int i = k/n;
        int j = k%n;
        return matrix[i][j];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 287. 寻找重复数 (opens new window)

方法一：二分

class Solution {
    public int findDuplicate(int[] nums) {
        int n = nums.length;
        int l=1,r=n-1;
        int ret = -1;
        while(l<=r){
            int mid = (l+r)>>1;
            int cnt = 0;
            for(int i=0;i<n;i++){
                if(nums[i]<=mid){
                    cnt++;
                }
            }
            if(cnt<=mid){
                l = mid+1;
            }else{
                r = mid-1;
                ret = mid;
            }
        }
        return ret;
    }
}

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

方法二：快慢指针

class Solution {
    public int findDuplicate(int[] nums) {
        int slow=0,fast=0;
        slow = nums[slow];
        fast = nums[nums[fast]];
        while(slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while(fast != slow){
            fast = nums[fast];
            slow = nums[slow];
        }
        return fast;
    }
}

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

← 状态机最大值最小问题→