Home Arrays [Leetcode] – Search Insert Position Solution

[Leetcode] – Search Insert Position Solution

by nikoo28
0 comment 3 mins read

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

a sample test case
Fig: Sample test case

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.

figure showing the search insert position
Fig: Search Insert Position

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.

a brute force solution approach
Fig: Brute Force Solution

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.
using binary search to reach the result
Fig: Using Binary Search


  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:

YouTube player

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More