# Search insert position

Category: Blog

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`.

## 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;
}
};
``````
Go
``````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

Python
``````class Solution:
def recursive_search(self, nums, target, left, right):
if left > right:
return left

mid = (left + right) // 2

if nums[mid] == target:
return mid
elif nums[mid] < target:
return self.recursive_search(nums, target, mid + 1, right)
else:
return self.recursive_search(nums, target, left, mid - 1)

def searchInsert(self, nums: List[int], target: int) -> int:
return self.recursive_search(nums, target, 0, len(nums) - 1)
``````
Java
``````class Solution {
public int searchInsert(int[] nums, int target) {
return recursiveSearch(nums, target, 0, nums.length - 1);
}

private int recursiveSearch(int[] nums, int target, int left, int right) {
if (left > right) {
return left;
}

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

if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
return recursiveSearch(nums, target, mid + 1, right);
} else {
return recursiveSearch(nums, target, left, mid - 1);
}
}
}
``````
C++
``````class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
return recursiveSearch(nums, target, 0, nums.size() - 1);
}

private:
int recursiveSearch(vector<int>& nums, int target, int left, int right) {
if (left > right) {
return left;
}

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

if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
return recursiveSearch(nums, target, mid + 1, right);
} else {
return recursiveSearch(nums, target, left, mid - 1);
}
}
};
``````
Go
``````func searchInsert(nums []int, target int) int {
return recursiveSearch(nums, target, 0, len(nums)-1)
}

func recursiveSearch(nums []int, target, left, right int) int {
if left > right {
return left
}

mid := left + (right-left)/2

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