搜索插入位置

比较简单的一题，就是寻找左侧边界的二分查找的思想，二分查找算法总结。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while(left <= right){
            int mid = left + (right-left)/2;
            if(nums[mid] >= target){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return left;
    }
}

当然也可以使用封装好的方法Arrays.binarySearch。

复杂度分析：

时间复杂度：$O(logn)$。
空间复杂度：$O(1)$。

1	class Solution {
2	public int searchInsert(int[] nums, int target) {
3	int left = 0;
4	int right = nums.length-1;
5	while(left <= right){
6	int mid = left + (right-left)/2;
7	if(nums[mid] >= target){
8	right = mid-1;
9	}else{
10	left = mid+1;
11	}
12	}
13	return left;
14	}
15	}