二分搜索
2020-05-27 18:52:12 # leetcode # 总结 # binary search

二分搜索

这里有一篇总结二分搜索非常好的Blog，链接贴在这，一定要看！！

传送门

一. 二分搜索基本应用场景

当一道题目出现了“有序N维数组中查找某个东西或最接近的值”时，大概率用二分搜索；或者输入的数字特别大，达到2^31 - 1左右的这种，也很有可能使用二分搜索。

其核心思想就是每次找一半，然后舍弃另一半，其中最恶心的莫过于有重复数字的二分搜索，太难顶了。例如：LeetCode 81的“Search in Rotated Sorted Array II”，到现在也不懂，真的难受，先记录着，等以后能搞懂了再回来看。

二. 二分搜索模板

基本模板

关于查找区间的问题，究竟是“左闭右开”还是“左右闭区间”，我在这里直接就用左右全闭区间的方法了。

1
2
3
4
5
6
7
8
9
10
11
while (l <= r) {
    m = l + (r - l) / 2;

    if g(m) == target :
        return;
    else if g(m) > target :
        r = m - 1;
    else if g(m) < target :
        l = m + 1;
}

最终返回的时候，l一定是r右面的那个数，这是由while的循环条件决定的，二者最后只能差1。最后看情况是需要l还是r。

左边界 & 右边界

参考题目：下面例题 3.4 LeetCode 34. Find First and Last Position of Element in Sorted Array

关于左边界和右边界的问题只要简单说一下就懂了，举个例子，我们有一个数组nums：[1, 2, 6, 6, 10, 13, 17]，我们想要找出数字6所在的位置，那么我们返回2还是返回3呢？虽然值是不同，但是对于实际应用的时候有很大不同。

比如说对于查找的时候，可能需要查找大于某个数的最小值，或者小于某个数的最大值，前者就是要找右边界，后者就是要找左边界(这里不敢保证写的绝对对啊，只是个人理解，有可能是错的)。

对于左右边界的处理其实不同点就在于等于的情况下，是更新left还是right。

左边界 -> 等于的时候更新右边界

1
2
3
4
5
6
7
8
while (l <= r) {
    m = l + (r - l) / 2;

    if g(m) >= target :
        r = m - 1;
    else if g(m) < target :
        l = m + 1;
}

右边界 -> 等于的时候更新左边界

1
2
3
4
5
6
7
8
while (l <= r) {
    m = l + (r - l) / 2;

    if g(m) > target :
        r = m - 1;
    else if g(m) <= target :
        l = m + 1;
}

返回l？返回r？

我们需要care的一点就是到底是返回l还是返回r呢？结论是：就题论题，九成以上返回l，但是不排除返回r的可能，例如上面的数组[1, 2, 6, 6, 10, 13, 17]，找出比6小的最大值，自己写一下代码，很容易发现返回的是r，而不是l，因此如果不确定的话，最好的办法是找个例子尝试一下。

三. 二分搜索简单题目

其实二分搜索，难的是真滴难，简单的也有很多坑，慢慢积累经验吧，有时候边界条件搞不懂就特别烦。

3.1 LeetCode 69. Sqrt(x)

注意：需要注意的点就是输入的值可能会特别大，二分后的值，如果直接平方的话有可能会越界，所以可以考虑使用除法或者用long来实现。这里用除法。

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 mySqrt(int x) {

        if (x <= 1) {
            return x;
        }

        int l = 0, m = 0, r = x;

        while (l <= r) {
            m = l + (r - l) / 2;
            if (m == x / m) {
                return m;
            } else if (m > x / m) {
                r = m - 1;
            } else if (m < x / m) {
                l = m + 1;
            }
        }

        return l - 1;
    }
}

3.2 LeetCode 367. Valid Perfect Square

注意：需要注意的是这里不能用除法，和69题不一样，因为除法会损失精度，导致计算错误，所以这里用long类型来辅助计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isPerfectSquare(int num) {
        int start = 1, end = num;
        long target = 0;

        while (start <= end) {
            target = (start + end) / 2;
            if (target * target > num) {
                end = (int)target - 1;
            } else if (target * target < num) {
                start = (int)target + 1;
            } else {
                return true;
            }
        }

        return false;
    }
}

3.3 LeetCode 35. Search Insert Position

注意：这道是最传统的二分搜索，基础中的基础。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, m = 0, r = nums.length - 1;

        while (l <= r) {
            m = l + (r - l) / 2;
            if (nums[m] == target) {
                return m;
            } else if (nums[m] < target) {
                l = m + 1;
            } else if (nums[m] > target) {
                r = m - 1;
            }
        }

        return l;
    }
}

3.4 LeetCode 34. Find First and Last Position of Element in Sorted Array

注意：先找到一个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
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length - 1, m = 0, pivot = -1;
        int[] res = new int[2];

        while (l <= r) {
            m = l + (r - l) / 2;
            if (nums[m] < target) {
                l = m + 1;
            } else if (nums[m] >= target) {
                r = m - 1;
            }
        }

        if (l == nums.length || nums[l] != target) {
            return new int[]{-1, -1};
        }

        // 这里l是第一个target的位置
        res[0] = l;

        r = nums.length - 1;
        while (l <= r) {
            m = l + (r - l) / 2;
            if (nums[m] > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        res[1] = l - 1;

        return res;
    }
}


3.5 LeetCode 50. Pow(x, n)

注意：这道题要用二分法来减少运算，次数，而且负数除以2余数为-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
class Solution {
    public double myPow(double x, int n) {
        if (x == 0d) {
            return 0;
        }

        if (n == 0) {
            return 1;
        } else if (n > 0) {
            double ret = myPow(x, n / 2);
            if (n % 2 == 1) {
                return x * ret * ret;
            } else {
                return ret * ret;
            }
        } else {
            double ret = myPow(x, n / 2);
            if ((0 - n) % 2 == 1) {
                return ret * ret / x;
            } else {
                return ret * ret;
            }
        }
    }
}
Prev
2020-05-27 18:52:12 # leetcode # 总结 # binary search
Next