[Leetcode] Search for a Range

Problem

Given a sorted array of integers, find the starting and ending position of a given target value. Your algorithm's runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Algorithm

1.  Binary search the target. Once found the target value, move left to find its left boundary, and move right to find its right boundary. Since the array may have O(n) target values, therefore, the running time is O(n). 

2. We can modify the binary search to find the left and right boundaries of the target value, 

The left boundary of the target window satisfies, 

A[m-1] < target and A[m] = target, 

and the right boundary satisfies, 

A[n+1] > target and A[n] = target.

This algorithm has O(log(n)) time, since half of the array are drop at each step. 

Code