Leetcode – Search for a Range (Java)

Tags: , , ,

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.