35. Search Insert Position

Loading...LeetCode

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

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;
    }
}

思路：

力扣

latest version

```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;
    }
}
```