Search Insert Position

Question (LC.35)

Given a sorted array and a target, return the index of the target if it exists or return the index in which target should be inserted.

Example

I: [1,3,5,6], 5
O: 2
I: [1,3,5,6], 2
O: 1

Linear Approach

Scan through the array linearly, find the target or a value bigger than the target

public int searchInsert(int[] nums, int target) {
    // good practice to check null or empty input
    if (nums == null || nums.length == 0) {
        return 0;
    }
    // linear scan
    int i;
    for (i = 0; i < nums.length; i++) {
        if (nums[i] >= target) {
            return i;
        }
    }
    return i;
}

This definite works. Can we do better?

Alternative Approach

Construct a binary search tree then search for the lower bound.

from sortedcontainers import SortedList 

class Solution:
   
   def searchInsert(self, nums: List[int], target: int) -> int:
       
       sorted_list = SortedList()
       for num in nums:
           sorted_list.add(num)
       
       return sorted_list.bisect_left(target)
       
       

Binary Search Example

Consider this example, given input [0,2,3,4,6,7,8,11] find target 6 with the search function below.

func search
    Pick a midpoint
    Check if the midpoint is the target, return it if so
    If smaller than the target, we search right section
    If bigger than the target,  we search left section

Tracing through this example

midpoint = 4, left = [0,2,3], right = [6,7,8,11]
midpoint < target, search right section

midpoint = 7, left = [6], right = [8,11]
midpoint > target, search left section

midpoint = 6, left = [6], right = [6]
return the index of 6

If we visualize this array as a binary search tree diagram,

               [0-11]
              /     \
    left  [0-3]    [6-11] right
         /    \      /  \
       [0]    [3]  [6] [8-11]
                          /  \
                        [8]  [11]

the worst case of going down a path is log(n), where n is the size of the input array. Because the binary tree is balanced and we have 2^height = n, $height = log_2(n) = O(log(n))$.

Recursive Implementation

A recursive implementation is intuitively sounding because we are applying the same search function either on the left or the right section.

public int searchInsert(int[] nums, int target) {
    // good practice to check null or empty input
    if (nums == null || nums.length == 0) {
        return 0;
    }
    return search(nums, 0, nums.length - 1, target);
}

private int search(int[] nums, int start, int end, int target) {
    // we want to stop when start and end are adjacent to each other
    if (start + 1 >= end) {
        if (target <= nums[start]) {
            return start;
        } else if (target <= nums[end]) {
            return end;
        } else {
            return end + 1;
        }
    }
    // binary search
    int midpoint = (start + end) / 2;
    if (nums[midpoint] == target) {
        return midpoint;
    } else if (nums[midpoint] < target) {
        return search(nums, midpoint + 1, end, target);
    } else {
        return search(nums, start, midpoint - 1, target);
    }
}

The stopping condition is doing a bit extra work here. We will see later that this method can be more convenient in other cases. For this question, we have three possible cases 1. target < A[start], return start 2. A[start] < target < A[end], return end 3. A[end] < target < A[end+1], return end + 1

Iterative Implementation

The recursion only keeps track of start index and end index. We can have two variables outside of the while loop to accomplish the same functionality.

public int searchInsert(int[] array, int target) {
    if (array == null || array.length == 0) {
        return 0;
    }
    int start = 0, end = array.length - 1;
    int mid;
    while (start + 1 < end) {
        mid = start + (end - start) / 2;
        if (array[mid] < target) {
            start = mid;
        } else {
            end = mid;
        }
    }
    // check the right place to insert
    if (target <= array[start]) {
        return start;
    } else if (target <= array[end]) {
        return end;
    } else {
        return end + 1;
    }
}

Time & Space Complexity

Recursive - O(logn) time (logn) space Iterative - O(logn) time O(1) space

The worst case of searching is going down a full path in the tree diagram above. The length of the full path or equivalently the height of the balanced tree is O(logn).

More formally, we can justify the runtime by solving the recurrence T(n) = T(n/2) + 1.

T(n) = T(n/2) + 1               --> 1
>    = [T(n/4) + 1] + 1         --> 2
>    = [[T(n/8) + 1] + 1] + 1   --> 3
    ...
>    = 1 + 1 + 1 ... + 1 + 1    --> lgn

Follow Up

What if we allow duplicates in the input array?