[LeetCode OJ]- Search Insert Po

题目要求是：给定一个数组，数组里面都是按升序拍好的数字，并且无重复数字；另外给一个比较的数字target，查找这个target在数组中是否出现，如果出现，返回出现的位置；如果没出现，返回应该“插入”的位置。

分析：这个问题其实就是对target与数组中的数字进行比较，如果采用暴利的方法，按顺序挨个查找，效率上不太好；因为这个数组是有顺序排列好的（升序），想到了一个快速查找的方法，二分查找。

二分查找的思想是：本质上是一种分治的策略，给定一个low指定最前端的位置，一个high指定最后端的位置，一个mid指定中间位置。每次进行比较时，比较mid位置上的值与target的大小，若target<nums【mid】，说明target一定在low到mid-1的位置中间，那么就把mid-1 赋给high；若target>nums【 mid】，target一定在mid+1 到high的位置中间，把mid+1赋给low；若target=num【mid】，此时的target的位置找到，返回位置……如此递归，直到low>high，结束递归。

以上是考虑的数组中有target的情况，那如果没有target怎么办呢？

模拟了三种情况：

1.target在数组的最左边。

nums=1,2,5,7,11，target=-4

当low>high时，此时的low恰好为target新插入的位置。

2.target在数组的最右边。

nums=1,2,5,7,11，target=888

当low>high时，此时的low恰好为target新插入的位置。

3.target在数组的中间。

nums=1,2,5,7,11，target=4

当low>high时，此时的low恰好为target新插入的位置。

那么算法就可以写成如下。

public class Solution {

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

int low,high;

low = 0;

high = nums.length - 1;

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

}

public int binSearch(int[] nums, int low, int high, int target){

while(low <= high){

int mid = (low + high)/2;

if(target < nums[mid]) return binSearch(nums, low, mid - 1, target);

else if(target > nums[mid]) return binSearch(nums, mid + 1, high, target);

else return mid;

}

return low;

}

}