35. Search Insert Position

Question

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

Algorithm

We could see from hint that we are asked to implement in a O(log n) time complexity. So binary search may be used here.

So we try to solve it use binary search.Forget about the first insert position, we just implement a binary search to find the target first; then we find that if target is not in the nums array, the left(or right because they are equal eventually) will be in the position of next insertion.

​ Why? Let's take an example,

Input: nums = [1,3,5,6], target = 7
Output: 4

We search the 7 until to the right of 6, finally left = right = 5, and it's the place where should be at. By using the binary search (left < right), we will traverse all the elements in the array and finally they will stop at the position which is the closest to the target. In contrast, target will be inserted to that position if possible.

Code

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