Using Binary Search to find insertion index

Consider a sorted input of unique elements[1,3,4,5,9,10] that we need to analyze to find the insertion location for a key, say 7. As clear from the input, the key is not present in the input and, if added, should be added at index 4 (0 based) to maintain the sorted nature of the input.

Also, as the input contains unique elements, we will return the existing index if the key is already present in the input array.

The brute-force approach will use linear search, where we simply iterate the input array and compare the key with every array element.

• If the key is found in the input, return its index.
• else, If the last element is smaller than the key, return lastIndex + 1
• otherwise, return the first index containing a value more than the key.

The worst-case complexity of this solution will be \(O(n)\) as we might end up traversing the complete input.

A better way to solve this problem is to use a variant of binary search where instead of returning a default value in case the key is unavailable, we return the index where it should be inserted, ensuring the sorted nature of the input. Let’s take a look at the following implementation:

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

As mentioned above, the algorithm will iterate over the input as long as \(start \leq end\). For the scenario where the key is not present in the input, it will go till both start and end point to the same element before terminating the loop.

Now, if the key is smaller than the element, the else part will execute, and via end = mid - 1, end will be updated, causing the loop to terminate. But as start still points to the smallest value greater than key, it represents the correct index where key should be inserted.

On the other hand, if the key is more than the element (largest value smaller than the key), the start index will be updated by start = mid+1, causing the loop to terminate as \(start \leq end\) is no longer valid. Now start points to 1 position to the right of the element, again the correct position for inserting the key and ensuring the sorted nature of the input.

The overall complexity of this algorithm remains as of binary search i.e. \(O(log_2n)\)