> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binarysearch/search_insert_position.md).

# 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)