leetCode 35.Search Insert Position (搜索插入位置) 解题思路和方法

Search Insert Position

[1,3,5,6], 0 → 0

思路：题目还是比较简单的，线性时间内可用循环遍历，不过也可以用二分查找，这样lgn的时间复杂度。

本文用二分实现，具体代码如下：

public class Solution {
    public int searchInsert(int[] nums, int target) {
    	//特殊情况
        if(nums.length == 0 || nums[0] > target)
            return 0;
        if(nums[nums.length - 1] < target)
        	return nums.length;
        //先二分查找，找到了就返回
        int low = 0;
        int hight = nums.length - 1;
        int mid = 0;
        while(low <= hight){
            mid = (low + hight)/2;
            if(nums[mid] < target){
                low = mid + 1;
            }else if(nums[mid] > target){
                hight = mid - 1;
            }else{
                return mid;
            }
        }
        //找不到再判断与nums[mid]大小，返回索引
        return nums[mid] > target?mid:mid+1;
    }
}

leetCode 35.Search Insert Position (搜索插入位置) 解题思路和方法

原文：http://blog.csdn.net/xygy8860/article/details/46818495