Find the Insert Position in Sorted Array

Find the Insert Position in Sorted Array


Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [1,3,5,6], target = 2

Output: 1
Explanation: Insert Position for 2 is 1. Index starts from 0. After insert array will look like this [1,2,3,5,6]

Example 2:

Input: nums = [1,3,5,6], target = 5

Output: 2
Explanation: 5 will be inserted after 3.

Example 3:

Input: nums = [1,3,5,6], target = 7

Output: 4
Explanation: 7 will be inserted as the last element after 6.

Linear Search Approach

Since the array is sorted, we can search through the array one by one. When array element >= target then insert position is  the current index position.

    int i; 
    for( i=0; i < nums.length; i++) 
        if(nums[i] >= target) 
        { return i; 

Time complexity: O(n) because we traverse whole array to find the insert position.
This is fairly simple but above approach is not accepted because in the question it is mentioned that we must solve in O(logN).
First thing that comes to our mind when see sorted array and O(logN) is Binary Search.

Binary Search Approach

We use Binary Search to find the insert position. Usually in binary search we find a particular element, but here we want to find the insert position. Consider the below cases before writing code.

case 1: Target Element is lesser than first element of array

case 2: Target Element is greater than last element of array

case 3: Target Element need to be inserted somewhere inside the array

During Binary Search if we reach start or end of the array( case 1 and case 2) and target is not found,  then insert position is 0 or n-1 respectively. 

Consider the following example,

Array: [1,3,5,6,7,8,9]

Target: 7

Find the Insert Position

Find the Insert Position

Find the Insert Position

Find the Insert Position




class Solution 
 public int searchInsert(int[] nums, int target) 
    int low = 0;
    int high = nums.length-1;
    int n = nums.length;
        int middle = (low+high)/2;

        if(nums[middle] > target )

            // when target is smaller than starting element of array
            // previous element is smaller and current element is larger than target
           if (middle == 0 || nums[middle-1] < target)
                return middle;
           high = middle-1;

        else if(nums[middle] < target)
            // target is larger than last element
            if(middle == n-1)
                return middle+1;
            low = middle+1;
            return middle;
    return -1;

You Might Also Like:

Maximum Subarray | Leetcode

How I got placed in Zoho

Follow For Instant Updates

Join WhatsApp Group: link
Join our Telegram Channel: link
Like our Facebook Page:  link
Subscribe to our Youtube channel: link

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.
5 1 vote
Article Rating
Notify of
Inline Feedbacks
View all comments
Would love your thoughts, please comment.x