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.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 4:

Input: [1,3,5,6], 0
Output: 0

有序的数组，查找固定的元素，很明显的二分查找

 1 int searchInsert(int* nums, int numsSize, int target) {
 2       /*当查找到最后，若没有找到，要是小于target，则返回index+1，
 3         若大于target,则返回target*/
 4     int low=0,high=numsSize-1;
 5     int mid,pos;
 6     while(low<=high){
 7         mid=(low+high)/2;
 8         if(nums[mid]==target)    return mid;
 9         if(nums[mid]<target)    low=mid+1;        
10         if(nums[mid]>target)    high=mid-1;    
11     }
12     
13     return nums[mid]>target?mid:mid+1;
14 }