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

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

在一個排好序的數組查找某值，存在則返回對應的value,不存在則返回能插入到數組中的index，  其實就是找到第一個大於等於目標值的下標。

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

解釋：

1、條件為target<=nums[mid]，意思是target小於等於中間值，則往左半區域查找。如在 {1,2,2,2,4,8,10}查找2，第一步，low=0, high=6, 得mid=3, target <= a[3]，往下標{1,2,2}中繼續查找。

2、終止前一步為: low=high，得mid = low，此時如果target <= nums[mid]，則high會改變，而low指向當前元素，即為滿足要求的元素。如果target > nums[mid]，則low會改變，而low指向mid下一個元素。

3、如果key大於數組最後一個元素，low最後變為nums.size()，即沒有元素大於key，返回 nums.size()。