Write a method named firstAndLastPosition
that returns the first and last indexes where a given value can be found in a sorted array.
Your method accepts two parameters: the sorted array and the value to search for, and returns a 2-element array containing the first and last indexes where the given value is found in the array, or {-1, -1}
if not found.
For example, if an array a
stores {-4, 1, 7, 7, 7, 7, 7, 9, 9, 15, 22}
, the call of firstAndLastPosition(a, 7)
would return {2, 6}
.
For the same array, the call of firstAndLastPosition(a, 15)
would return {8, 8}
and the call of firstAndLastPosition(a, 5)
would return {-1, -1}
.
The challenge of this problem comes from trying to solve it as efficiently as possible.
An optimal solution can run in O(log N) time for an array of length N.
You may assume that the array is in sorted order.