Search for a Range

Question (LC.34)

Given a sorted array of integers, find the starting and ending position of a given target value.

G - phone interview

Example

Input: [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

Ask edge cases: if target doesn't exist in the array, return [-1, -1].

Analysis

Finding a target in a sorted array. Classic binary search setup.
Initial thought: find first or last index then for loop to find the range. runtime will be O(log(n) + range).
On a second thought, we can just do two binary searches. 1. find the first pos 2. find the last pos