[LeetCode] 35. Search Insert Position

Posted on | In

Problem

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:

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

Example 2:

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

Example 3:

1
2
Input: [1,3,5,6], 7
Output: 4

Example 4:

1
2
Input: [1,3,5,6], 0
Output: 0

Explanation

  1. First, we check if the target is greater than the last element of the array. If it is, then we just return the last index of the array plus one.

  2. Next, we can use binary search to find the left most position of the target, but if we find some number equals to target, in other words, nums[mid] == target, we can just return mid. Outside the loop of left < right, that means left and right pointers both point to the same element, we can just return left as the result index that the target should be added to.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        if (target > nums[right]) {
            return right+1;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}