Search insert position

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.

In programming and computer science, efficiently searching and managing data is crucial. One common problem is finding the position of a target value in a sorted array of distinct integers. If the target is not present, the goal is to determine the index where it should be inserted to maintain the array's sorted order. This problem can be solved efficiently using the binary search algorithm, which offers a time complexity of O(log n).

Problem statement

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 inserted in order.

Example

Example 1

Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Explanation: The target value 5 is found at index 2.

Example 2

Input: nums = [1, 3, 5, 6], target = 2
Output: 1
Explanation: The target value 2 is not present in the array. It should be inserted at index 1 to maintain sorted order.

Example 3

Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Explanation: The target value 7 is greater than all elements in the array and should be inserted at the end, index 4.

Problem link

Solution 1: Using Linear Search

The first solution that comes to our mind is using a linear search. We can traverse each element in the array and find out the correct position of the component.

The time complexity of this solution will be O(n) because we are traversing each element in the array. Since the elements in the array are sorted we can do it better.

Solution 2: Using Binary Search

We can use binary search here because the elements in the array are in sorted order.

Implement simple binary search, if the element exists in the array then we will return the element as we do in case of binary search.

If that element does not exist in the array then the loop gets over then we know either the left pointer will be equal to the right pointer or they might have crossed each other. This could be the only case.

So, we can perform a simple check at the end, if the element at the left pointer is less than the target then return the left index otherwise the position next to the left pointer will be the correct position for the element to be inserted.

Search(Arr, target)
    left = 0
    right = len(Arr) - 1

    while left < right:
        mid = (left + right) / 2

        if Arr[mid] == target:
            return mid
        else if Arr[mid] < target:
            left = mid+1
        else:
            right = mid-1

    if Arr[left] < target:
        return left+1
    else:
        return left

We can further tweak the actual binary search to make it better.

We know that we have to check the elements till left <= right then we can avoid checking the elements later after the end of the loop.

Initialization: Start with two pointers, left and right, which represent the current search range. Initially, left is 0 and right is the last index of the array.
Binary Search Loop:
- Calculate the middle index, mid, as the average of left and right.
- Compare the target value with the element at index mid:
  - If nums[mid] == target, the target is found, and mid is returned.
  - If nums[mid] < target, the target must be in the right half of the current range, so set left = mid + 1.
  - If nums[mid] > target, the target must be in the left half of the current range, so set right = mid - 1.
Termination: The loop terminates when left exceeds right. At this point, left will be the position where the target should be inserted if it is not present in the array.

Search(Arr, target)
    left = 0
    right = len(Arr) - 1

    while left <= right:
        mid = (left + right) / 2

        if Arr[mid] == target:
            return mid
        else if Arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return left

Now let's implement this solution.

Python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = (left + right) // 2

            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1

        return left

Java

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
}

C++

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
};

func searchInsert(nums []int, target int) int {
    left, right := 0, len(nums) - 1

    for left <= right {
        mid := left + (right - left) / 2

        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return left
}

Using recursive binary search