Problem - Search Insert Position (Second problem)

Given a sorted array and a target value, return the index where the target is found. If not found, return the index where it would be inserted to keep the array sorted.

For example, given $[1, 3, 5, 6]$ and target $5$, return $2$. Given target $2$, return $1$ (insert between $1$ and $3$).

The sorted array is your clue. You can use binary search to find the position in $O(\log n)$ time instead of scanning the entire array.