[Leetcode] – Search Insert Position Solution

903

According to the given problem statement, we are provided a sorted array of distinct integers, and a target value. You need to search the insert position of this element such that the resultant array will remain in an increasing order. We desire a time complexity of O(\log n).

Let us understand the problem easily by a sample test case.

Input: arr = [ 1, 3, 5, 6 ]
Target value = 2
Output: 1

Now, if 2 needs to be inserted in the array, it will come between 1 and 3, such that the array remains in a non-decreasing order. Theoretically, we search the insert position of the element we want to add.

Brute Force Solution:

A pretty straight forward approach is a brute force solution where we start from the beginning of the array and keep on moving ahead until we see elements smaller than the target value.

As we traverse, we reach the element 15, and then we see 17. It clearly shows that we need to insert the element between these 2 elements and the position should be [5]. All the other elements shift once the insert actually happens.

This approach will work in O(n) time, but we need something faster.

Using Binary Search:

When we target a time complexity around O(\log n), Binary Search should be at the top of your mind. That is how we divide the problem into 2 halves and proceed.

The approach here will be very simple:

• Choose a low index as the [0] index
• The high index will be the last element of the array.
• Get the mid point by mid = low + \frac{(high - low)}{2}
• Check if the target value is greater than the left element, and smaller than the right element.
• If yes, this is the search insert position, else update the low and high index accordingly.

Code:

  public int searchInsert(int[] nums, int target) {

    int low = 0;
    int high = nums.length - 1;

    while (low <= high) {
      int mid = low + (high - low) / 2;

      if (nums[mid] == target) {
        return mid;
      } else if (nums[mid] > target) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }

    return low;
  }
Code language: Java (java)

Time Complexity: O(\log n)
Space Complexity: O(1)

Video Explanation: