This one is a binary search-related problem. Click here to see the problem in LeetCode.
We will be given a sorted array in ascending order. And a target value. So, what do we have to do? We will have to return the index of the target value. If the target value is not in the given array, we will have to return the index where it would be if it were inserted in order.
It’s an easy problem. First, how do we find an element in a sorted array? The answer is Binary Search. It is the most efficient way to search in a sorted array. In Binary Search, if the element is in the array, the function returns its position.
In this case, If we found the target value, the problem is solved. But if the target value is not in the array? What would be the index if it would be inserted? The answer is that we will return the ‘left‘ index after the Binary Search completion instead of -1.
Think about it why it works this way? Look at the code. Try to apply a simple example in this code first. Do it in your mind first.
I hope we all know the Binary Search algorithm. It is one of the most common algorithms.
Let’s see the solution in 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 target > nums[mid]:
left = mid + 1
else:
right = mid - 1
return left
Time complexity: O(log n)
Space complexity: O(1)
This is the solution to this problem. I hope you got the idea.
Happy Coding 🙂
Keep Practicing 🙂