[LeetCode] Search for a Range (Java)

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].


In fact, in this problem, we are going to use binary search to find the border of certain target, because there may be duplicate numbers. We can easily find the left border of certain target. And we can try to find the left border of target + 1. And check if it exists to determine the right border.



It’s O(log n).