Search for a Range

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

EXAMPLE:

Given [5, 7, 7, 8, 8, 10] and target value 8,

return [3, 4].

Solution: (Python)

The problem can be divided into two binary searches. One search for the lower boundary of the target in the array, while the other search for the higher boundary. Initial two variable: low = 0, high = len(nums)-1

Suppose in each step, mid = (low+high)/2. There are three cases: (e.g. the left boundary)

1. If nums[mid] < target, then the range starts on the right of mid; -- low= mid+1
2. If nums[mid] > target, then the range starts on the left of mid; -- high = mid-1
3. If nums[mid] = target, the range starts on the left of mid or at mid; -- high = mid

Consequently, when the range of low and high shrinks to two, i.e low + 1 = high, there are several possible cases:

(target = 5)

case 1: [5, 7] nums[low] = target < nums[high]
case 2: [5, 5] nums[low] = target = nums[high]
case 3: [3, 5] nums[low] < target = nums[high]
case 4: [6, 7] target < nums[low] < numw[high]
case 5: [3, 4] target > nums[low] > numw[high]
case 6: [4, 6] nums[low] < target < nums[high]

1. After case 1 & 2, high = low, loop terminates, target found.
2. After case 3, low = high, loop terminates, target found.
3. After other cases, no target found in the returned result. Simply return [-1, -1]

For the right boundary, the possible cases are the same with the left boundary cases:

1. If nums[mid] < target, the range ends on the right of mid; -- low = mid + 1
2. If nums[mid] > target, the range ends one the left of mid; -- high = mid - 1
3. If nums[mid] = target, the range ends on the left of mid or at mid; -- low = mid

Similarily, for the six cases above:

1. After case 1 & 2, low remains the same, so the boundary doesn't change. (PROBLEM HERE!)
2. After 3, low = high, target found
3. The other cases are impossible here.

Solution to the PROBLEM:

For the left boundary situation, actully the mid is biased to the left, i.e like mid = math.floor((low + high) / 2); so for the right boundary, we bias the mid to the right, i.e mid = math.ceil((low + high) / 2) (or mid = (low + high) / 2 + 1)

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        ans = [-1, -1]
        # search for the element smaller than the target
        low = 0
        high = len(nums) - 1
        while low < high:
            mid = int((low+high)/2)
            if nums[mid] == target:
                high = mid
            elif nums[mid] > target:
                high = mid-1
            elif nums[mid] < target:
                low = mid + 1
        if nums[low] != target: return ans
        ans[0] = low

        low = 0
        high = len(nums) - 1
        while low < high:
            mid = int((low+high)/2) + 1
            if nums[mid] == target:
                low = mid
            elif nums[mid] < target:
                low = mid + 1
            elif nums[mid] > target:
                high = mid - 1
        ans[1] = high

        return ans