leetcode: Search for a Range

Problem Description:

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

Solution and Precautions:

Binary search for the left bound in the sequence of the target, do another binary search for the right bound. The tricky point is that even when you found a target, you still need to search the left for the left bound and search the right for the right bound. Write a recursive solution might be a better choice here. Things would be very tricky.

Note once you find a position for the target, you continue to BINARY SEARCH rather than the linear scan to find possible more left bound. If you can’t find more left bound, return the current position you just find (e.e.  8 9 10, 8 and you find 8, you return 8). If you find a more left bound, you return the real left bound (e.g.  8 8 8 9 10, 8 and you find the second 8, then you continue to search the left bound, you will find the first 8, you should return the position of the first 8).

Tips and Divergent thinking:

Don't do linear search to find the left bound and right bound once you find the target in the sequence by binary search. In the extreme case, all the numbers are the same in the sequence. This approach becomes O(N) rather than O(logN).

Written on June 12, 2013