“Search Insert Position” Problem

Photo by Mika Baumeister on Unsplash

Problem :

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:

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 :

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Abdullah Afzal

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