“Search Insert Position” Problem
Problem :
Search Insert Position O (Log n) | Binary Search
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.
[1,3,5,6]
5
Output: 2
[1,3,5,6]
2
Output: 1
[1,3,5,6]
7
[1,3,5,6]
0
Solution:
The solution to the problem is the Binary Search as given as a Hint with the problem statement.
If you don’t know about Binary Search then check this article first
But here is a little variation to do in Binary Search for this problem. When the target value is not found then check whether the latest mid value of the array is smaller than the target value, if it is smaller than the target value, then it will be after that index.
And if the latest mid-index value of the array is not smaller then simply return the mid-index as the target value will be placed at that index.
Code :
