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

相关源码：code

1 | 关于二分查找的一些trick： |

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

解题思路：本题数组为**有序** ，并且题目要求**查找** ，自然而然会想到二分查找，代码如下：

1 | bool isBadVersion(int version); |

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

解题思路：基本思路就是树的遍历，利用完全二叉树的性质优化程序，代码如下：

1 | class Solution { |

## 29. Divide Two Integers

Description:

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

解题思路：利用减法，加之**移位** 操作**优化** ，代码如下：

1 | class Solution { |

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

解题思路：**经典题型** ，先找到最小值的位置，然后“平移”数组，代码如下：

1 | class Solution { |

## 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:**

1 | Input: [ [1,2] ] |

**Example 2:**

1 | Input: [ [3,4], [2,3], [1,2] ] |

**Example 3:**

1 | Input: [ [1,4], [2,3], [3,4] ] |

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

1 | struct Interval { |

## 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，即从两个反方向进行，代码如下：

1 | class Solution { |

## 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:**

1 | Input: |

代码如下：

1 | class Solution { |

## 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:

1 | [ |

Given **target** = `3`

, return `true`

.

解题思路：将二维数组按照一维数组进行处理，属于index search, 代码如下：

1 | class Solution { |

## 81. Search in Rotated Sorted Array II

Description:

Follow upfor “Search in Rotated Sorted Array”:

What ifduplicatesare allowed?Would this affect the run-time 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.

解题思路：旋转数组问题关键是找到最小值位置，代码如下：

1 | class Solution { |

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

解题思路：动态规划，代码如下：

1 | class Solution { |

## 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:**

1 | Input: |

**Note:**

- 1 <= len(A), len(B) <= 1000
- 0 <= A[i], B[i] < 100

解题思路：动态规划，代码如下：

1 | class Solution { |

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

解题思路：旋转数组，代码如下：

1 | class Solution { |

## 230. Kth Smallest Element in a BST

Description:

Given a binary search tree, write a function `kthSmallest`

to find the **k**th 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.

解题思路：本质就是计数，代码如下：

1 | struct TreeNode { |

## 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:

1 | [ |

Given **target** = `5`

, return `true`

.

Given **target** = `20`

, return `false`

.

解题思路：**经典题** ，代码如下：

1 | class Solution { |

## 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:**

1 | matrix = [ |

**Note: **

You may assume k is always valid, 1 ≤ k ≤ n2.

解题思路：本题很经典，此题属于range search，代码如下：

1 | class Solution { |

## 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:**

1 | Input: [1,2,3,4,5], k=4, x=3 |

**Example 2:**

1 | Input: [1,2,3,4,5], k=4, x=-1 |

**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个元素，代码如下：

1 | class Solution { |

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

解题思路：双指针法，代码如下：

1 | class Solution { |

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

解题思路：代码如下：

1 | class Solution { |