二分查找

正长实现

1
2
3
Input : [1,2,3,4,5]
key : 3
return the index : 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class binary{
    public int binarySearch(int[] nums,int key){
        int l =0,h = nums.length - 1;
        while(l<=h){
            int m = l + (h - l) / 2;
            if(nums[m] == key){
                return m;
            }else if(nums[m] < key){
                l = m + 1;
            }else{
                h = m - 1;
            }
        }
        return -1;
    }
}

时间复杂度

二分查找也称为折半查找，每次都能将查找区间减半，这种折半特性的算法时间复杂度为 O(logN)。

计算m

有两种计算中值 m 的方式：

  • m = (l + h) / 2
  • m = l + (h - l) / 2

l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。所以，最好使用第二种计算法方法。

返回值

循环退出时如果仍然没有查找到 key，那么表示查找失败。可以有两种返回值：

  • -1：以一个错误码表示没有查找到 key
  • l：将 key 插入到 nums 中的正确位置

变种

二分查找可以有很多变种，实现变种要注意边界值的判断。例如在一个有重复元素的数组中查找 key 的最左位置的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
public int binarySearch2(int[] nums, int key){
        int l =0,h = nums.length - 1;
        while(l<h){
            int m = l + (h - l) / 2;
            if(nums[m] >= key){
               h = m;
            }else{
               l = m + 1;
            }
        }
        return l;
    }

该实现和正常实现有以下不同：

  • h 的赋值表达式为 h = m
  • 循环条件为 l < h
  • 最后返回 l 而不是 -1

在 nums[m] >= key 的情况下，可以推导出最左 key 位于 [l, m] 区间中，这是一个闭区间。h 的赋值表达式为 h = m，因为 m 位置也可能是解。

在 h 的赋值表达式为 h = m 的情况下，如果循环条件为 l <= h，那么会出现循环无法退出的情况，因此循环条件只能是 l < h。以下演示了循环条件为 l <= h 时循环无法退出的情况：

1
2
3
4
5
6
7
nums = {0, 1, 2}, key = 1
l   m   h
0   1   2  nums[m] >= key
0   0   1  nums[m] < key
1   1   1  nums[m] >= key
1   1   1  nums[m] >= key
...

求开方

力扣

要注意int数值的范围。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int mySqrt(int x) {
        if (x <= 1) {
            return x;
        }
        int l = 1, h = x;
        while (l <= h) {
            int m = l + (h - l) / 2;
            int sqrt = x / m;
            if (sqrt == m) {
                return m;
            } else if (sqrt < m) {
                h = m - 1;
            } else {
                l = m + 1;
            }
        }
        return h;
    }
}

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

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public char nextGreatestLetter(char[] letters, char target) {
        int n = letters.length;
        int l = 0, h = n - 1;
        while (l <= h) {
            int m = l + (h - l) / 2;
            if (letters[m] <= target) {
                l = m + 1;
            } else {
                h = m - 1;
            }
        }
        return l < n ? letters[l] : letters[0];
    }
}

有序数组中的单一元素

力扣

异或的时间复杂度为O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int l = 0, h = n - 1;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (m % 2 == 1) {
                m = m - 1;
            }
            if (nums[m] == nums[m + 1]) {
                l = m + 2;
            } else {
                h = m;
            }
        }
        return nums[l];
    }
}

第一个错误的版本

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 1, h = n;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (isBadVersion(m)) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

寻找旋转排序数组中的最小值

力扣

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findMin(int[] nums) {
        int l = 0, h = nums.length - 1;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (nums[m] < nums[h]) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        return nums[l];
    }
}

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

力扣

可以用二分查找找出第一个位置和最后一个位置，但是寻找的方法有所不同，需要实现两个二分查找。我们将寻找 target 最后一个位置，转换成寻找 target+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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int first = findFirst(nums, target);
        int last = findFirst(nums, target + 1) - 1;
        if (first == nums.length || nums[first] != target) {
            return new int[]{-1, -1};
        } else {
            return new int[]{first, Math.max(first, last)};
        }
    }

    private int findFirst(int[] nums, int target) {
        int l = 0, h = nums.length;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (nums[m] >= target) {
                h = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while (left<=right){
            int mid = left + (right-left)/2;
            if(target>nums[mid]){
                left=mid+1;
            }else if(target<nums[mid]){
                right=mid-1;
            }else {//target==nums[mid]
                while (nums[left]!=target) left++;
                while (nums[right]!=target) right--;
                return new int[]{left,right};
            }
        }
        return new int[]{-1,-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
class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int l = 1, h = Arrays.stream(piles).max().getAsInt();
        while (l < h) {
            int m = l + (h - l) / 2;
            if (canEat(piles, m, H)) {
                h = m;
            } else {
                l = m + 1;
            }

        }
        return l;
    }

    private boolean canEat(int[] piles, int speed, int H) {
        int sum = 0;
        for (int pile : piles) {
            if (pile % speed > 0) {
                sum += pile / speed + 1;
            } else {
                sum += pile / speed;
            }
        }
        return sum <= H;
    }
}

寻找旋转排序数组中的最小值Ⅱ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findMin(int[] nums) {
        int l = 0, h = nums.length - 1;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (nums[m] > nums[h]) {
                l = m + 1;
            } else if (nums[m] < nums[h]) {
                h = m;
            } else {//key position
                h--;
            }
        }
        return nums[l];

    }
}

供暖器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        int res = 0;
        int n = heaters.length;
        Arrays.sort(heaters);
        for (int house : houses) {
            int l = 0, h = n - 1;
            while (l < h) {
                int m = l + (h - l) / 2;
                if (heaters[m] < house) {
                    l = m + 1;
                } else {
                    h = m;
                }
            }
            int dist1 = h == n ? Integer.MAX_VALUE : Math.abs(house - heaters[h]);
            int dist2 = h == 0 ? Integer.MAX_VALUE : Math.abs(house - heaters[h - 1]);
            res = Math.max(res, Math.min(dist1, dist2));
        }
        return res;
    }
}