【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，那么删除这一行。

 1 class Solution {
 2 public:
 3     bool searchMatrix(vector<vector<int>>& matrix, int target) {
 4         if (matrix.empty() || matrix[0].empty()) {
 5             return false;
 6         }
 7         const int n = matrix.size(), m = matrix[0].size();
 8         int up = 0, right = m-1;
 9         while (up < n && right >= 0) {
10             if (matrix[up][right] == target) {
11                 return true;
12             }
13             if (matrix[up][right] < target) {
14                 up++;
15             } else if (matrix[up][right] > target) {
16                 --right;
17             }
18         }
19         return false;
20     }
21 };

View Code

【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。同理右半区间一样。

 1 class Solution {
 2 public:
 3     int findPeakElement(vector<int>& nums) {
 4         const int n = nums.size();
 5         int left = 0, right = n - 1;
 6         while (left < right) {
 7             int mid = (left + right) / 2;
 8             int target = nums[mid+1];
 9             if (nums[mid] < target) {
10                 left = mid + 1;
11             } else {
12                 right = mid;
13             }
14         }
15         return left;
16     }
17 };

View Code

【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.

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

 1 class Solution {
 2 public:
 3     bool searchMatrix(vector<vector<int>>& matrix, int target) {
 4         if (matrix.empty() || matrix[0].empty()) {
 5             return false;
 6         }
 7         const int n = matrix.size(), m = matrix[0].size();
 8         int up = 0, right = m-1;
 9         while (up < n && right >= 0) {
10             if (matrix[up][right] == target) {
11                 return true;
12             }
13             while (up < n && matrix[up][right] < target) {
14                 ++up;
15             }
16             if (up == n) { break; }
17             while (right >= 0 && matrix[up][right] > target) {
18                 --right;
19             }
20         }
21         return false;
22     }
23 };

View Code

【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 自己实现

 1 // Forward declaration of isBadVersion API.
 2 bool isBadVersion(int version);
 3 
 4 class Solution {
 5 public:
 6     int firstBadVersion(int n) {
 7         long long left = 0, right = (long long)n + 1;
 8         long long mid;
 9         while (left < right) {
10             mid = left +  (right - left) / 2;
11             if (!isBadVersion(mid)) {
12                 left = mid + 1;
13             } else {
14                 right = mid;
15             }
16         }
17         return left;
18     }    
19 };

View Code

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

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

题解：解法1. sort + 2 pointers

 1 class Solution {
 2 public:
 3     int findDuplicate(vector<int>& nums) {
 4         sort(nums.begin(), nums.end());
 5         for (int i = 0; i < nums.size() - 1; ++i) {
 6             if (nums[i] == nums[i+1]) {
 7                 return nums[i];
 8             }
 9         }
10         return -1;
11     }
12 };

View Code

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

【300】Longest Increasing Subsequence 

【302】Smallest Rectangle Enclosing Black Pixels 

【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!

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

 1 // Forward declaration of guess API.
 2 // @param num, your guess
 3 // @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
 4 int guess(int num);
 5 
 6 class Solution {
 7 public:
 8     int guessNumber(int n) {
 9         int left = 1, right = n;
10         long long mid;
11         while (left <= right) {
12             mid = (long long)left + (right - left) / 2;
13             int res = guess(mid);
14             if (res == 0) {
15                 return mid;
16             } else if (res < 0) { //leftside
17                 right = mid - 1;
18             } else {
19                 left = mid + 1;
20             }
21         }
22         return -1;
23     }
24 };

View Code

【378】Kth Smallest Element in a Sorted Matrix 

【392】Is Subsequence 

【410】Split Array Largest Sum 

【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+了。

 1 class Solution {
 2 public:
 3     int arrangeCoins(int n) {
 4         int k = my_upper_bound(1, (long long)n + 1, (long long)n * 2);
 5         return k - 1;
 6     }
 7     int my_upper_bound(int begin, long long end, long long target) {
 8         long long mid = 0;
 9         while (begin < end) {
10             mid = ((long long)begin + end) / 2;
11             long long temp = mid * (mid + 1);
12             if (temp > target) {
13                 end = mid;
14             } else {
15                 begin = mid + 1;
16             }
17         }
18         return begin;
19     }
20 };

View Code

【454】4Sum II 

【475】Heaters 

【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 

【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 

【862】Shortest Subarray with Sum at Least K 

【875】Koko Eating Bananas 

【878】Nth Magical Number 

【887】Super Egg Drop 

【LeetCode】二分 binary_search（共58题）

原文：https://www.cnblogs.com/zhangwanying/p/9886707.html