本文主要是对leetcode中的binary search类算法的总结，包含了各题的solution和常用的解决方法。
相关源码：code


278. First Bad Version
Description:
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n
versions [1, 2, ..., n]
and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version)
which will return whether version
is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
解题思路：本题数组为有序 ，并且题目要求查找 ，自然而然会想到二分查找，代码如下：


222. Count Complete Tree Nodes
Description:
Given a complete binary tree, count the number of nodes.
Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
解题思路：基本思路就是树的遍历，利用完全二叉树的性质优化程序，代码如下：


29. Divide Two Integers
Description:
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
解题思路：利用减法，加之移位 操作优化 ，代码如下：


33. Search in Rotated Sorted Array
Description:Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
You are given a target value to search. If found in the array return its index, otherwise return 1.
You may assume no duplicate exists in the array.
解题思路：经典题型 ，先找到最小值的位置，然后“平移”数组，代码如下：


436. Find Right Interval
Description:
Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.
For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store 1 for the interval i. Finally, you need output the stored value of each interval as an array.
Note:
 You may assume the interval’s end point is always bigger than its start point.
 You may assume none of these intervals have the same start point.
Example 1:


Example 2:


Example 3:


解题思路：我们需要对区间排序，并且需要记录原有索引，所以使用map 数据结构；然后使用二分查找找到相应的区间，代码如下：


34. Search for a Range
Description:
Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm’s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [1, 1]
.
For example,
Given [5, 7, 7, 8, 8, 10]
and target value 8,
return [3, 4]
.
解题思路：此题属于index search,数组中会出现多个相同的目标值，我们需要确定起始和终止的位置。这样的话，其实我们需要做两次BS，即从两个反方向进行，代码如下：


454. 4Sum II
Description:
Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l)
there are such that A[i] + B[j] + C[k] + D[l]
is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of 228 to 228  1 and the result is guaranteed to be at most 231  1.
Example:


代码如下：


74. Search a 2D Matrix
Description: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.
For example,
Consider the following matrix:


Given target = 3
, return true
.
解题思路：将二维数组按照一维数组进行处理，属于index search, 代码如下：


81. Search in Rotated Sorted Array II
Description:
Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?Would this affect the runtime complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
解题思路：旋转数组问题关键是找到最小值位置，代码如下：


300. Longest Increasing Subsequence
Description:Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18]
,
The longest increasing subsequence is [2, 3, 7, 101]
, therefore the length is 4
. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
解题思路：动态规划，代码如下：


718. Maximum Length of Repeated Subarray
Description:
Given two integer arrays A
and B
, return the maximum length of an subarray that appears in both arrays.
Example 1:


Note:
 1 <= len(A), len(B) <= 1000
 0 <= A[i], B[i] < 100
解题思路：动态规划，代码如下：


153. Find Minimum in Rotated Sorted Array
Description:
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
Find the minimum element.
You may assume no duplicate exists in the array.
解题思路：旋转数组，代码如下：


230. Kth Smallest Element in a BST
Description:
Given a binary search tree, write a function kthSmallest
to find the kth smallest element in it.
**Note: **
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
解题思路：本质就是计数，代码如下：


240. Search a 2D Matrix II
Description:
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.
For example,
Consider the following matrix:


Given target = 5
, return true
.
Given target = 20
, return false
.
解题思路：经典题 ，代码如下：


378. Kth Smallest Element in a Sorted Matrix
Description:
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
Example:


**Note: **
You may assume k is always valid, 1 ≤ k ≤ n2.
解题思路：本题很经典，此题属于range search，代码如下：


658. Find K Closest Elements
Description:Given a sorted array, two integers k
and x
, find the k
closest elements to x
in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.
Example 1:


Example 2:


Note:
 The value k is positive and will always be smaller than the length of the sorted array.
 Length of the given array is positive and will not exceed 104
 Absolute value of elements in the array and x will not exceed 104
UPDATE (2017/9/19):
The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.
解题思路：先找到x（大于x的第一元素）在数组中的位置，然后在此位置周围找到k个元素，代码如下：


209. Minmum Size Subarray Sum
Description:
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.
For example, given the array [2,3,1,2,4,3]
and s = 7
,
the subarray [4,3]
has the minimal length under the problem constraint.
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
解题思路：双指针法，代码如下：


287. Find the Duplicate Number
Description:
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.
Note:
 You must not modify the array (assume the array is read only).
 You must use only constant, O(1) extra space.
 Your runtime complexity should be less than
O(n2)
.  There is only one duplicate number in the array, but it could be repeated more than once.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
解题思路：代码如下：

