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.
The insert position is the index which element’s value is greater or equal with target.
So we scan linearly the array will find the answer.
Approach with Binary Search
When the target element is in array, binary search will found the position in time complexity of $O(logN)$.
For an increasing array, if the target is not in array, the ended
lo pivot will be the index of element with value larger or equal with target.
Preparing for an interview? Check out this!