# 35. Search Insert Position

{% embed url="https://leetcode.com/problems/search-insert-position/" %}



**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
```

```java
class Solution {
    public int searchInsert(int[] nums, int target) {
        int length = nums.length;
        if (length == 0) return 0;
        
        if (target > nums[length - 1]) {
            return length;
        }

        
        int left = 0;
        int right = length - 1;
        
        
        while (left  < right) {
            int mid = (left + right) >>> 1; 
            
            // 1,2,3,4,5,9   target: 7
            // we want to insert to 9's index, 
            // so we want to insert to a num >= target
            // num < target is not we want
            if (nums[mid] < target) { // it's not we want
                // [mid+1, right]
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
```

思路：

{% embed url="https://leetcode-cn.com/problems/search-insert-position/solution/te-bie-hao-yong-de-er-fen-cha-fa-fa-mo-ban-python-/" %}



### latest version

````java
```java
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) {
                return mid;
            } else if (nums[mid] > target) {
                if (mid - 1 >= 0 && nums[mid-1] < target || mid == 0) {
                    return mid;
                }

                right = mid - 1;
            } else {
                if (mid + 1 < nums.length - 1 && nums[mid+1] > target || mid == nums.length - 1) {
                    return mid + 1;
                }
                left = mid + 1;
            }
        }
        return -1;
    }
}
```
````

