Given a sorted array of numbers, we would like to search for a specific number. Implement a function that returns the index of that number, or if it is not in the array, the index where it would be.
For example, for
[1, 3, 5, 16],
For simplicity, assume if the number exists in the array, there will only be one instance of it. Try to solve the problem in less than a linear time.
search([ 1, 3, 5, 16 ], -1);