Coder's Cat

2020-02-03

## Challenge Description

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.

Example 1:

Example 2:

## Naive Solution

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.

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!