Posted Updated Leetcode7 minutes read (About 1013 words)0 visits

Binary Search总结

Binary Search And Search Problem总结

Search问题的核心思想只有一个，就是每一步都会减少搜索域

Binary Search的核心思想是：每次只取搜索域的一半，舍弃另一半，我们的搜索域不断一半一半的减小最后找到结果，所以时间复杂度才会是O(logn)
Binary search有固定的书写模板，容易出现问题的点是判断终止条件，主要有三种写法：start<=end，start<end，start+1<end。
我觉得采用第三种写法比较好，因为不会出现死循环的问题(比如使用start<end，但是更改条件的时候写的是start=mid，这就会造成死循环，mid一直等于start，start又一直等于mid)，不过需要在最后判断一下left和right指针的结果。但是有的题型还是会用其他写法。

left<=right的写法，left必须等于mid+1，right必须等于mid-1，否则会出现死循环，因为edge case是left==right的时候，这个时候mid等于left等于right，如果我们不加1和减1，就会死循环
left<right的写法，left必须等于mid+1，right可以等于mid。因为edge case是left+1==right的时候，这个时候mid等于left，如果left不加1就会死循环，记住在结束以后需要判断left的值
left+1<right的写法，left和mid都可以等于mid，但是记住在结束以后需要判断left和right的值

Binary Search By Index

Rotated Array类型题：

  1. Search in Rotated Sorted Array：最重要的一道题，主要的思想是如果我们的pivot在左半部分(3456712)，那么rotated的数组的左半部分是递增的，也就是我们如果我们的value在左半部分这一递增的区间，我们就可以扔掉右半部分只管左半部分，反之亦然。
    所以我们可以看出来关键就是要每次舍弃掉一半的搜索区间。

follow-up是数组中会有重复的数，这样的情况下做法是把重复的情况单独拎出来

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
class Solution {
    public int search(int[] nums, int target) {
        if(nums.length==0)
            return -1;
        int left = 0;
        int right = nums.length-1;
        while(left+1<right){
            int mid = left + (right-left)/2;
            if(nums[mid]==target)
                return mid;
            
            if(nums[left]<nums[mid]){
                if(target>=nums[left] && target<=nums[mid]){
                    right = mid;
                }
                else {
                    left = mid;
                }
            }
            else {
                if(target>=nums[mid] && target<=nums[right]){
                    left  = mid;
                }
                else {
                    right = mid;
                }
            }
        }
        
        if(nums[left]==target)
            return left;
        else if(nums[right]==target){
            return right;
        }
        else {
            return -1;
        }
    }
}
  1. Search in Rotated Sorted Array II: 需要多考虑一下如果nums[left]==nums[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
class Solution {
    public boolean search(int[] nums, int target) {
        if(nums.length==0)
            return false;
        int left = 0;
        int right = nums.length-1;
        while(left+1<right){
            int mid = left + (right-left)/2;
            if(nums[mid]==target)
                return true;
            
            if(nums[left]<nums[mid]){
                if(target>=nums[left] && target<=nums[mid]){
                    right = mid;
                }
                else {
                    left = mid;
                }
            }
            else if(nums[left]>nums[mid]){
                if(target>=nums[mid] && target<=nums[right]){
                    left  = mid;
                }
                else {
                    right = mid;
                }
            }
            else {
                left++;
            }
        }
        
        if(nums[left]==target)
            return true;
        else if(nums[right]==target){
            return true;
        }
        else {
            return false;
        }
    }
}

  1. Find Minimum in Rotated Sorted Array:与上面两道题类似，考虑三种情况：不rotated；rotated的pivot在左半部分；rotated的pivot在右半部分：
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
class Solution {
    public int findMin(int[] nums) {
        
        int start = 0;
        int end = nums.length-1;
        while(start+1<end){
            int mid = start + (end-start)/2;
            //none-rotated
            if(nums[start]<nums[end]){
                return nums[start];
            }
            
            
            if(nums[start]<nums[mid]){//pivot on left part
                start = mid;
            }
            else {//pivot on right part
                end = mid;
            }
        }
        if(nums[start]<nums[end])
            return nums[start];
        else
            return nums[end];
    }
}
  1. Find Minimum in Rotated Sorted Array II
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
class Solution {
    public int findMin(int[] nums) {
        
        int start = 0;
        int end = nums.length-1;
        while(start+1<end){
            int mid = start + (end-start)/2;
            //none-rotated
            if(nums[start]<nums[end]){
                return nums[start];
            }
            
            if(nums[start]<nums[mid]){//pivot on left part
                start = mid;
            }
            else if((nums[start]>nums[mid])) {//pivot on right part
                end = mid;
            }
            else {
                start++;
            }
        }
        if(nums[start]<nums[end])
            return nums[start];
        else
            return nums[end];
    }
}

Search Matrix类型题：

  1. Search a 2D Matrix:很简单，就当做一个连续的array就好。
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
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m==0)
            return false;
        int n = matrix[0].length;
        if(n==0)
            return false;
        
        int start = 0;
        int end = m*n-1;
        while(start+1<end){
            int mid = start+ (end-start)/2;
            int row = mid/n;
            int column = mid%n;
            if(matrix[row][column]==target){
                return true;
            }
            else if(matrix[row][column]<target){
                start = mid;
            }
            else{
                end = mid;
            }

        }

        if(matrix[start/n][start%n]==target || matrix[end/n][end%n] ==target)
            return true;
        else
            return false;
    }
}
  1. Search a 2D Matrix II：算是binary search的一种变种吧，本质上还是要减少搜索的空间。所以我们不从左上或者右下开始搜索，而是从右上或者左下，这样每次我们都能确定往何处移动。
    时间复杂度是O(m+n)
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 boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        if(m==0)
            return false;
        int n = matrix[0].length;
        int i = m-1;
        int j = 0;
        while(i>=0 && j<=n-1){
            if(matrix[i][j] == target){
                return true;
            }
            else if(matrix[i][j]<target){
                j++;
            }
            else {
                i--;
            }
        }
        return false;
    }
}

Binary Search By Range:

类似的题目和很好的总结：https://leetcode.com/problems/k-th-smallest-prime-fraction/discuss/115819/Summary-of-solutions-for-problems-%22reducible%22-to-LeetCode-378
https://leetcode.com/problems/find-k-th-smallest-pair-distance/discuss/109082/Approach-the-problem-using-the-%22trial-and-error%22-algorithm

  1. Find the Duplicate Number:这道题有两个做法，第一个做法是LinkedList Cycle II的思想(见LinkedList Cycle类型题)。第二个做法就是Binary Search By Range。这道题我们最大的number是数组的长度减一，也就是说重复的数一定在这个范围内，我们使用binary search，start是1，end是最大number，然后我们每次search都遍历数组并统计小于等于mid的数量，如果这个数量大于mid，由鸽巢原理我们确认这个重复的数一定在左半部分，否则在右半部分，这就相当于每次减少了搜索域。
    We know that the whole range is “too crowded” and thus that the first half or the second half of the range is too crowded (if both weren’t, then neither would be the whole range). So you check to know whether the first half is too crowded, and if it isn’t, you know that the second half is.

想这种问题的时候不要去想为什么我们这样by range search最后的结果会在array中呢？这样想很容易就会绕进去出不来了！我们要明确这时候我们是search by range而不再是search by index，search by index的时候我们当然知道元素一定在array中，而search by range的时候我们需要知道的就是：已知结果在这个range中，我们确保结果一直在搜索域，经过不断收敛那么最后一定会找到结果，那这个结果也就自然而然一定在array中了。
有一个点需要注意：与普通的binary search不同，我们的判断条件没有count==K，因为即使等于也不代表找到的是那个number，有可能略大于，但也正好有K个count，所以一定要等到最后收敛完成

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 findDuplicate(int[] nums) {
        int start = 1;
        int end = nums.length-1;
        while(start<end){
            int mid = start + (end-start)/2;
            int count = 0;
            for(int num:nums){
                if(num<=mid)
                    count++;
            }
            
            if(count>mid){
                end = mid;
            }
            else {
                start = mid+1;
            }
        }
        return start;
    }
}
  1. Kth Smallest Element in a Sorted Matrix：首先拿到这道题，我们看到Kth这个关键词就要往top k问题去想，topK问题的解决方法无外乎PriorityQueue, Quick Select两种办法。所以我们最简单可以想到的就是使用PriorityQueue(见Top K总结)。
    另一个想法是binary search，但是按照普通的binary search的search by index我们发现并不能解决这个问题，所以应该采用的是search by range(也就是根据number的range进行搜索)。By range搜索会有一个count，这里就是K，我们每次进行binary search，然后统计小于等于mid的count，然后和K进行比较进行搜索域的减小。

这道题在进行小于等于mid的count计数的时候有一个巧妙方法，就是利用240题目类似的方法，从右上或左下开始找，这样只需要O(n)就可以找到小于等于mid的个数，所以时间复杂度是O(nlogn)

  1. Kth Smallest Number in Multiplication Table
  2. Find K-th Smallest Pair Distance
  3. K-th Smallest Prime Fraction

其他binary search类型题：

  1. Median of Two Sorted Arrays：很难的题目，告诉了我们binary search不仅局限在可以search index/range，也可以search index与index之间的split点。这道题的核心思想是median的作用是把数组分成两部分，左半部分的值一定小于右半部分，所以我们在第一个array中找到一个split点，第二个array的split点也就随之确定了，我们需要确保第一个array split点的左侧的number小于第二个array split点的右侧的number以及第二个array split点的左侧的number小于第一个array split点的右侧的number，对于split点的选择，自然而然可以选择binary search。
    ps.1 Why n >= m? Because I have to make sure j is non-nagative since 0 <= i <= m and j = (m + n + 1)/2 - i. If n < m , then j may be nagative, that will lead to wrong result.
    https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn)))-solution-with-explanation
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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if(m>n){
            return findMedianSortedArrays(nums2, nums1);
        }
        int start = 0;
        int end = nums1.length;
        while(start<=end){
            int mid1 = start + (end-start)/2;
            int mid2 = (m+n+1)/2-mid1;
            if(mid1>0 && mid2<n && nums1[mid1-1]>nums2[mid2]){
                end = mid1-1;
            }
            else if(mid1<m && mid2>0 && nums1[mid1]<nums2[mid2-1]){
                start = mid1+1;
            }
            else {//perfect match
                //corner case
                int leftMax = 0;
                int rightMin = 0;
                if(mid1==0)
                    leftMax = nums2[mid2-1];
                else if(mid2==0)
                    leftMax = nums1[mid1-1];
                else{
                    leftMax = Math.max(nums2[mid2-1], nums1[mid1-1]);
                }
                
                if((m+n)%2!=0)
                    return leftMax;
                
                if(mid1==m){
                    rightMin = nums2[mid2];
                }
                else if(mid2==n){
                    rightMin = nums1[mid1];
                }
                else {
                    rightMin = Math.min(nums2[mid2], nums1[mid1]);
                }

                return (leftMax+rightMin)/2.0;

                
            }
             
        }
        return -1.0;
    }
}
Follow

Catalogue

×