LeetCode. 35. Search Insert Position

Problem

Approach

Use binary search to find the lower bound: the first index whose value is greater than or equal to target. Maintain a half-open search interval [left, right). At the start, it contains every valid array index. At each step, left is a boundary before which every value is less than target, while right is a boundary at or after which every value is at least target. If the midpoint value is less than target, move left past it; otherwise, move right to the midpoint. The interval shrinks until left == right, which is the lower-bound index. If every value is smaller, that index is nums.length; an empty array naturally returns zero. Choosing the first value that is at least the target also handles duplicates.

The search takes O(log N) time and O(1) auxiliary space.

Java

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) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}