Search Insert Position

https://leetcode.com/problems/search-insert-position/description/

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.

Thoughts

lowerBound的直接应用，找到该元素或者第一个比它大的数所在位置．end 取n因为可能插在所有元素的后面。

Code

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

Analysis

时间复杂度O(lgn)