// 參考http://blog.csdn.net/u014221279/article/details/51546739class Solution {public:    int searchInsert(vector<int>& nums, int target)         {        // 邊界檢查        int n = nums.size();        if (n == 0) return -1;                // 二分法        // 包括了target < nums[0] 或 target > nums[n - 1]的情況        // 當 target == nums[mid]時，   直接找到了"原數"；        // 當 最終nums[mid] < target時，說明"原數"不存在，會找到"比原數大一個的數"(此時low > high終止循環)        int low = 0;        int high = n - 1;               // 若nums的長度為 1 也ok。((n == 1) ? n : n - 1);        int mid;                while(low <= high)        {            mid = low + (high - low) / 2;            if(nums[mid] == target)                return mid;            else if(nums[mid] < target) // 在右半部分繼續找                low = mid + 1;            else                        // 在左半部分繼續找                high = mid - 1;         }        return low;                     // 因為找的是"原數"(若原數存在) 或 "比原數大一個的數"(若原數不存在)，故返回low。    }};
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
Subscribe to see which companies asked this question.
已排序的數組中如果有要插入的數組子，直接返回下標，即mid。
若沒有，則會一直查到到low》high  此時 返回low即可