# Search Insert Position

**Easy**

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.

**Example 1:**

```
Input:
 [1,3,5,6], 5

Output:
 2
```

**Example 2:**

```
Input:
 [1,3,5,6], 2

Output:
 1
```

**Example 3:**

```
Input:
 [1,3,5,6], 7

Output:
 4
```

**Example 4:**

```
Input:
 [1,3,5,6], 0

Output:
 0
```

## Analysis

此题用Template 1，2都能比较简洁地得到答案。

其实要找的是第一个恰好比target大的数的index。

用template#1，最后剩余2个数的情况下，left在倒数第一循环中，因为right-left=1，所以mid其实就是left，因为比target小，则循环跳出后left其实就变成left+1，比target大了。

## Solution

Template #1

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

        return left;
    }
}
```

Template #2

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

        return left;
    }
}
```

Template #3

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

        if (target > nums[right]) {
            return right + 1;
        }
        if (target > nums[left]) {
            return left + 1;
        }
        return left;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/binary-search/search-insert-position.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.