“Search Insert Position” Problem

Abdullah Afzal
2 min readAug 10, 2022

--

Photo by Mika Baumeister on Unsplash

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

Binary Search Algorithm

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 :

--

--

Abdullah Afzal

A student, always trying to look up for cool things and do something creative.