【LeetCode】二分 binary_search（共58题）

【4】Median of Two Sorted Arrays 

【29】Divide Two Integers 

【33】Search in Rotated Sorted Array 

【34】Find First and Last Position of Element in Sorted Array 

【35】Search Insert Position 

【50】Pow(x, n) 

【69】Sqrt(x) 

【74】Search a 2D Matrix （2019年1月25日，谷歌tag复习）剑指offer原题

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true 

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

题解：用 target 和当前右上角元素做比较，如果相等返回 true，如果不想等，如果右上角元素大于target，那么删除这一列，如果右上角元素小于target，那么删除这一行。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) {
            return false;
        }
        const int n = matrix.size(), m = matrix[0].size();
        int up = 0, right = m-1;
        while (up < n && right >= 0) {
            if (matrix[up][right] == target) {
                return true;
            }
            if (matrix[up][right] < target) {
                up++;
            } else if (matrix[up][right] > target) {
                --right;
            }
        }
        return false;
    }
};

  

【81】Search in Rotated Sorted Array II 

【153】Find Minimum in Rotated Sorted Array 

【154】Find Minimum in Rotated Sorted Array II 

【162】Find Peak Element （2018年11月27日）（本题需要复习，一开始不会做的。我觉得二分也容易写错的。）

这题要求我们在一个无序的数组里找到一个peak元素，所谓peak，就是值比两边邻居大就可以了。

题解：对于这道题目，最简单的解法就是遍历数组，只要找到第一个符合要求的元素就可以了，时间复杂度为O（n），但是这题要求O(LogN)的时间复杂度，还可以用二分来做。https://blog.csdn.net/NK_test/article/details/49926229

首先我们找到中间节点mid，如果大于两边返回当前的index就可以了，如果左边的节点比mid大，那么我们可以继续在左半区间查找，这里面一定存在一个peak，为什么这么说呢？假设此时的区间范围为[0,mid-1]，因为num[mid-1]一定大于num[mid]，如果num[mid-2]<=num[mid-1]，那么num[mid-1]就是一个peak。如果num[mid-2]>num[mid-1]，那么我们就继续在[0,mid-2]区间查找，因为num[-1]为负无穷，所以我们最终绝对能在左半区间找到一个peak。同理右半区间一样。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        const int n = nums.size();
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            int target = nums[mid+1];
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

2019年4月15日更新。我们可以根据mid和旁边元素的大小来移动指针。我们的目标其实是把搜索方向放到元素增大的一侧。

如果我们把二分写成如下的形式，那么可以发现，当 left = right 的时候退出循环，mid 永远取不到 right，那么 mid + 1 也就永远合法。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        const int n = nums.size();
        int left = 0, right = n-1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < nums[mid+1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

【167】Two Sum II - Input array is sorted 

【174】Dungeon Game 

【209】Minimum Size Subarray Sum 

【222】Count Complete Tree Nodes 

【230】Kth Smallest Element in a BST 

【240】Search a 2D Matrix II (2019年1月26日，谷歌tag复习)

write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted in ascending from left to right.
• Integers in each column are sorted in ascending from top to bottom.

题解：很多种方法可以做，我还是每次看右上角元素。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) {
            return false;
        }
        const int n = matrix.size(), m = matrix[0].size();
        int up = 0, right = m-1;
        while (up < n && right >= 0) {
            if (matrix[up][right] == target) {
                return true;
            }
            while (up < n && matrix[up][right] < target) {
                ++up;
            }
            if (up == n) { break; }
            while (right >= 0 && matrix[up][right] > target) {
                --right;
            }
        }
        return false;
    }
};

【270】Closest Binary Search Tree Value （）

【275】H-Index II 

【278】First Bad Version (2018年12月22日，地里面经)

给了一个数字 n， 代表数组 [1..n]，给了一个 api， bool isBadVersion(int version); 能判断一个数字是不是 bad version。在调用这个给定的api最小次数的前提下，返回这个数组中第一个bad version。

题解：二分，lower_bound 自己实现

// Forward declaration of isBadVersion API.
bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        long long left = 0, right = (long long)n + 1;
        long long mid;
        while (left < right) {
            mid = left +  (right - left) / 2;
            if (!isBadVersion(mid)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }    
};

【287】Find the Duplicate Number （2019年1月26日，二分查找）

给了一个nums数组，里面包含 1 — n-1 的数字，有一个数字可能重复了2次到多次。找出来这个数。

题解：解法1. sort + 2 pointers

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 1; ++i) {
            if (nums[i] == nums[i+1]) {
                return nums[i];
            }
        }
        return -1;
    }
};

解法2. 二分==总写错啊

【300】Longest Increasing Subsequence 

【302】Smallest Rectangle Enclosing Black Pixels （2019年1月26日，谷歌tag题）

给了一个矩阵，0代表白色像素，1代表黑色像素，黑色所有的像素是四联通的，问把黑色所有像素的包围起来的最小矩形面积。

题解：这题是个二分 tag，但是我只会用dfs解法。dfs解法时间复杂度是O(mn)的。我们需要找四个值，1像素的最左，最右，最上和最下。然后用矩阵的长和宽相乘一下就可以了。

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        if (image.size() == 0 || image[0].size() == 0) {
            return 0;
        }
        n = image.size(), m = image[0].size();
        vector<vector<int>> visit(n, vector<int>(m, 0));
        left = right = y;
        top = buttom = x;
        dfs(image, x, y, visit);
        int area = (right - left + 1) * (buttom - top + 1);
        return area;
    }
    int n, m;
    int left = -1, right = -1, top = -1, buttom = -1;
    void dfs(const vector<vector<char>>& image, int x, int y, vector<vector<int>>& visit) {
        visit[x][y] = 1;
        left = min(left, y), right = max(right, y);
        top = min(top, x), buttom = max(buttom, x);
        for (int k = 0; k < 4; ++k) {
            int newx = x + dirx[k], newy = y + diry[k];
            if (newx >= 0 && newx < n && newy >= 0 && newy < m && image[newx][newy] == '1' && !visit[newx][newy]) {
                dfs(image, newx, newy, visit);
            }
        }
        return;
    }
    int dirx[4] = {-1, 0, 1, 0};
    int diry[4] = {0, -1, 0, 1};
};

【349】Intersection of Two Arrays （2018年11月6日，算法群相关题）

hash-table 里面有这题，hash-table：https://www.cnblogs.com/zhangwanying/p/9886262.html

也可以二分解答，二分没有想过，我估计就是先排序，然后二分吧

【350】Intersection of Two Arrays II （2018年11月6日，算法群）

hash-table 里面有这题，hash-table：https://www.cnblogs.com/zhangwanying/p/9886262.html

也可以二分解答，二分没有想过，我估计就是先排序，然后二分吧

【354】Russian Doll Envelopes 

【363】Max Sum of Rectangle No Larger Than K 

【367】Valid Perfect Square 

【374】Guess Number Higher or Lower （2019年1月25日，谷歌tag复习）

在 [1, n] 这个区间里面猜数，给了一个 guess 的api，返回一开始 pick 的数字。

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

题解：二分，这题我写成了左闭右闭的形式。

// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;
        long long mid;
        while (left <= right) {
            mid = (long long)left + (right - left) / 2;
            int res = guess(mid);
            if (res == 0) {
                return mid;
            } else if (res < 0) { //leftside
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
};

【378】Kth Smallest Element in a Sorted Matrix (2019年2月9日)

给了一个 n * n 的矩阵，返回矩阵中第 k 小的元素。

题解：二分答案。我们要找到一个最小的元素x，满足矩阵中的元素小于等于x的值的有k个。（lower_bound）

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        const int n = matrix.size();
        int left = matrix[0][0], right = matrix[n-1][n-1] + 1;
        while (left < right) {
            int mid = left + ((right - left) / 2);
            int tot = 0;
            for (auto& row : matrix) {
                auto iter = upper_bound(row.begin(), row.end(), mid);
                tot += distance(row.begin(), iter);
            }
            // printf("left = %d, right = %d, mid = %d, tot = %d
", left, right, mid, tot);
            if (tot < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

【392】Is Subsequence 

【410】Split Array Largest Sum （2019年3月2日，谷歌tag）

给了一个连续的数组，每个元素代表任务完成的时间，然后给了一个天数m，要求这些任务必须在m天之内完成（可以提前）但是这些任务必须按顺序做，求最小化这这些天花在任务上时间的最大值。

举个例子：

nums = [7,2,5,10,8]
m = 2

Output:
18

Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.

题解：我们其实可以枚举这个时间，我们假设一天最多做 k 个小时，看 m 天之内能不能完成。如果不能的话，我们尝试扩大k，如果可以的话，我们尝试缩小k。所以二分查找的思路就出来了。left 边界是数组的最大值，right边界是整个数组的和。

整体时间复杂度是 O(nlogn)

class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        const int n = nums.size();
        long long left = -1, right = 0;
        for (auto& num : nums) {
            right += num;
            if (num > left) {
                left = num;
            }
        }
        int res(-1);
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            if (check(nums, mid, m)) {
                res = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return res;
    }
    bool check(vector<int>& nums, long long mid, int m) {
        int cnt = 0; long long sum = 0LL;
        for (auto num : nums) {
            if (sum + num <= mid) {
                sum += num;
            } else {
                cnt++;
                sum = num;
                if (cnt == m || sum > mid) {return false;}
            }
        }
        return true;
    }
};

【436】Find Right Interval 

【441】Arranging Coins (2018年11月26日)

给了 n 枚硬币， 我们排列这些硬币，第一行放1个，第二行放2个，.. ，第 k 行放 k 个。问这 n 个硬币最多能完全放满多少行。

题解：我一个解法是用 等差数列的公式求解的， k * (k + 1) <= 2 * n。 枚举 k， 找到最大满足条件的 k，然后 返回 k . 这个解法只能 beats 20%+。

后来我看是二分的tag，我就写了一个 二分，然后就beats 90+了。

class Solution {
public:
    int arrangeCoins(int n) {
        int k = my_upper_bound(1, (long long)n + 1, (long long)n * 2);
        return k - 1;
    }
    int my_upper_bound(int begin, long long end, long long target) {
        long long mid = 0;
        while (begin < end) {
            mid = ((long long)begin + end) / 2;
            long long temp = mid * (mid + 1);
            if (temp > target) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }
};

【454】4Sum II

 

【475】Heaters （2019年2月26日）

给了一个房子数组和一个暖气数组，求暖气的最小半径，要求所有的房子必须被暖气覆盖。

题解：对于每一个房子求离它最近的暖气，用 lower_bound 求，然后用这个半径和 global_max 做比较。时间复杂度是 O(nlogn)

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(heaters.begin(), heaters.end());
        int res = 0;
        for (auto& pos : houses) {
            auto iter = lower_bound(heaters.begin(), heaters.end(), pos);
            int radius = 0;
            if (iter == heaters.begin()) {
                radius = *iter - pos;
            } else if (iter == heaters.end()) {
                --iter;
                radius = pos - *iter;
            } else {
                radius = min(*iter - pos, pos - *(iter-1));
            }
            res = max(res, radius);
        }
        return res;        
    }
};

【483】Smallest Good Base 

【497】Random Point in Non-overlapping Rectangles 

【528】Random Pick with Weight 

【644】Maximum Average Subarray II 

【658】Find K Closest Elements 

【668】Kth Smallest Number in Multiplication Table 

【702】Search in a Sorted Array of Unknown Size (2019年1月26日，二分查找复习，谷歌tag，lower_bound思想, M)

给了一个不知道长度的array，问target是否存在在array中。ArrayReader.get(k) 能获取 index = k的值。数据范围： 

You may assume all integers in the array are less than 10000, and if you access the array out of bounds, ArrayReader.get will return 2147483647.

1. You may assume that all elements in the array are unique.
2. The value of each element in the array will be in the range [-9999, 9999].

题解：我推算出数组最长为 20000，所以left = 0， right = 20000，直接用lower_bound, 如果说 reader.get(mid) 这个数字是 INT_MAX 的话，right = mid，丢弃所有右边的。如果说 reader.get(mid) < target 的话，那么说明，mid 这个依旧不满足条件，我们需要把整个左边和mid一起丢掉 left = mid + 1。剩下的话，就是 right = mid

// Forward declaration of ArrayReader class.
class ArrayReader;

class Solution {
public:
    int search(const ArrayReader& reader, int target) {
        long long left = 0, right = 20000, mid = 0;
        while (left < right) {
            mid = (left + right) / 2;
            int temp = reader.get(mid);
            if (temp == INT_MAX) {
                right = mid;
            } else if (temp < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (reader.get(left) == target) {
            return left;
        }
        return -1;
    }
};

【704】Binary Search 

【710】Random Pick with Blacklist 

【718】Maximum Length of Repeated Subarray 

【719】Find K-th Smallest Pair Distance 

【744】Find Smallest Letter Greater Than Target 

【774】Minimize Max Distance to Gas Station 

【778】Swim in Rising Water 

【786】K-th Smallest Prime Fraction 

【793】Preimage Size of Factorial Zeroes Function 

【852】Peak Index in a Mountain Array (2019年2月27日，google tag)

给了一个三角顺序的数组，（前半段递增，后半段递减），返回值最大的元素下标。

Example 1:
Input: [0,1,0]
Output: 1
Example 2:
Input: [0,2,1,0]
Output: 1 

题解：二分，如果遍历一遍就行的话，这就不应该是一个面试题。时间复杂度是 O(logN)

如果 nums[mid] < nums[mid+1], 说明mid还在递增的区间，我们这个时候应该++left。

不然如果  nums[mid-1] < nums[mid] > nums[mid+1]，说明mid已经是我们寻找的目标值。

再或者 nums[mid-1] > nums[mid], 说明现在已经在递减的区间。我们应该 right = mid

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& A) {
        const int n = A.size();
        int left = 0, right = n;
        while (left < right) {
            int mid = (left + right) / 2;            
            if (mid + 1 < right && A[mid] < A[mid+1]) {
                left = mid + 1;
            } else if (mid - 1 >= left && A[mid-1] < A[mid]) {
                return mid;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

【862】Shortest Subarray with Sum at Least K 

【875】Koko Eating Bananas 

【878】Nth Magical Number 

【887】Super Egg Drop