Wiki
In computer science, binary search, also known as halfinterval search or logarithmic search, is a search algorithm that finds the position of a target value within a sorted array. It compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful.
Binary search runs in at worst logarithmic time, making O(logn) comparisons, where n is the number of elements in the array and log is the binary logarithm; and using only constant O(1) space. Although specialized data structures designed for fast searching—such as hash tables—can be searched more efficiently, binary search applies to a wider range of search problems.
Although the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions
and midpoint calculation
.
Implementation issues
If the midpoint of the span is calculated as (L + R) / 2, then the value of L + R may exceed the range of integers of the data type used to store the midpoint, even if L and R are within the range. This can be avoided by calculating the midpoint as L + (R − L) / 2.
An infinite loop may occur if the exit conditions for the loop—or equivalently, recursive step—are not defined correctly. Once L exceeds R, the search has failed and must convey the failure of the search. In addition, the loop must be exited when the target element is found, or in the case of an implementation where this check is moved to the end, checks for whether the search was successful or failed at the end must be in place.
If the search space consists only of integers, test your algorithm on a twoelement set to be sure it doesn’t lock up
Verify that the lower and upper bounds are not overly constrained: it’s usually better to relax them as long as it doesn’t break the predicate
Clarify what exactly you are looking for and then make sure each round your searching space will not lose it
Examples
Valid Perfect Square
ven a positive integer num, write a function which returns True if num is a perfect square else False.
Note: Do not use any builtin library function such as sqrt.
Example 1:
Input: 16
Returns: True
Example 2:
Input: 14
Returns: False


Longest Increasing Subsequence
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?


More C++ way using lower_bound, which means the previous binary search is doing the lower_bound
thing.


Find the Duplicate Number
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.


Another neat solution using loop searching technique.


First Bad Version
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.


HIndex II
Given an array of citations (each citation is a nonnegative integer) of a researcher, write a function to compute the researcher’s hindex.
According to the definition of hindex on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”
For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his hindex is 3.
Note: If there are several possible values for h, the maximum one is taken as the hindex.
What if the citations array is sorted in ascending order? Could you optimize your algorithm?


if we change the termination to
l <= r
then correspondinglyr = m1
Search a 2D Matrix II
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, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.


Find Minimum in Rotated Sorted Array II
Suppose a sorted array 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. The array may contain duplicates.


Search in Rotated Sorted Array II
Follow up for “Search in Rotated Sorted Array”: What if duplicates are allowed? Write a function to determine if a given target is in the array.


Conclusion
 termination
l < r
r = m
andl = m+1
and after searchingl == r
 termination
l <= r
r = m1
andl = m+1
and after searchingl > r
 always clearly know what you are searching for and keep that valid in the searching space