Given a sorted array 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.
You may assume no duplicates in the array.
Okay so the array is sorted
We have to find out where the given number would be inserted
this sounds like a binary search problem
Well brute force algorithm would be the easiest But it won’t be efficient
Binary search would give us
We can do some border cases before even starting our binary algorithm
ex: if target is less than first number from the array return 0
ex: if target is greater than last number from the array return
last index + 1
I use this logic to get the
const mid = Math.floor((high-low)/2 + low)
I have used recursion here
But, you can use simple
while loop for the binary search
I believe that should give you a better runtime
Ask questions like
Will the array contain negative numbers
Will there be duplicate the the array What would be the result in case of duplicate numbers
How big would be the array Will it fit in memory
Sample test cases
This may not be the optimal solution. And that’s okay. The purpose here is to practice problem solving and have fun with algorithms. I am constantly learning new optimized solutions for these problems.
Please comment below if you have a better solution. Let’s learn algorithms and data structures together.