# Leetcode – Search for a Range (Java)

### Search for a Range

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

Analysis:

This problem is equivalent to find the lower bound and upper bound of the target value in the sorted array.

For instance, given a sorted array` [1, 2, 2, 2, 2, 3, 3, 4, 5],` the lower bound for `2` is index `1`. and the upper bound for `2` is index `4`.

Since the array is sorted, we can use the idea of binary search to get the index of the lower bound and upper bound.

Given an array `nums[left .. right]`, we first calculate the middle index `mid = (left + right) / 2.`

In binary search, the algorithm immediately returns when `nums[mid] == target`

However, in the search for lower bound or upper bound, when `nums[mid] == target`, we know the index `mid` is just a candidate of the lower bound or upper bound, so we use a variable `res` to record its value.

To find the lower bound, we need to continue search the array `nums[left .. mid - 1]`

Similarly, to find upper bound, we need to continue search the array `nums[mid + 1 .. right].`

For the other cases, they are the same as binary search.

Specifically, when `nums[mid] < target`,  the target is in the right side.

When `nums[mid] > target`, the target is in the left side.

The following code shows the solution for the search range problem in Java.