(java) 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

思路：用2分查找，找到那个位置，当low>high时 return high+1；当是最小时返回0，当是最大时返回length；

代码如下(已通过leetcode)

public class Solution {

   public int searchInsert(int[] nums, int target) {

       int position=generate(nums,target,0,nums.length-1);

       return position;

   }

private int generate(int[] nums, int target, int low, int high) {

// TODO Auto-generated method stub

if(low>high) return high+1;

int mid=(low+high)/2;

if(nums[mid]==target) return mid;

else {

if(nums[mid]>target) high=mid-1;

else low=mid+1;

return generate(nums, target, low, high);

}

}

}