35.LeetCode-- Array--Search Insert Position(在已排序数组内找元素（该元素可能存在或不存在）)

// 参考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即可