## 二分查找模板总结

• start + 1 < end
• start + (end - start) / 2
• A[mid] ==, <, >
• A[start] A[end] ? target

• 头尾指针，取中点，判断往哪儿走
• 寻找满足某个条件第一个或是最后一个位置
• 保留剩下来一定有解的那一半

https://www.lintcode.com/en/problem/classical-binary-search/

Find any position of a target number in a sorted array. Return -1 if target does not exist.

Given [1, 2, 2, 4, 5, 5].

For target = 2, return 1 or 2.

For target = 5, return 4 or 5.

For target = 6, return -1.

### Question 2: First Position of target

For a given sorted array (ascending order) and a target number, find the first index of this number in O(log n) time complexity.

If the target number does not exist in the array, return -1.

If the array is [1, 2, 3, 3, 4, 5, 10], for given target 3, return 2.

### Question 4: search-insert-position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume NO duplicates in the array.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

### Question 5: Search in a big sorted array

Given a big sorted array with positive integers sorted by ascending order. The array is so big so that you can not get the length of the whole array directly, and you can only access the kth number by ArrayReader.get(k) (or ArrayReader->get(k) for C++). Find the first index of a target number. Your algorithm should be in O(log k), where k is the first index of the target number. Return -1, if the number doesn't exist in the array.