34. Search for a Range

Problem from leetcode 34. Search for a Range

---

为了达到O(logn)的时间复杂度效果，我们需要进行两次binary search，一次是找range的左边界，一次是找range的右边界。

---

这种情况我们需要小心边界测试。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int size = nums.size();
        
        int low = 0, high = size-1;
        while(low <= high)
        {
            int mid = low+(high-low)/2;
            if(nums[mid] < target) 
                low = mid+1; 
            else 
                high = mid-1; 
        } 
        if(high+1 >= size || nums[high+1] != target)
            return vector<int>(2, -1);
        
        vector<int> result(2);
        result[0] = high+1;
        
        low = high+1, high = size-1;
        while(low <= high) 
        { 
            int mid = low+(high-low)/2; 
            if(nums[mid] > target)
                high = mid-1;
            else
                low = mid+1;
        }
        
        result[1] = low-1;
        return result;
    }
};

Java:

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = result[1] = -1;
        
        int size = nums.length;
        if(size == 0) return result;
        
        int low = 0, high = size-1;
        //try to find the left edge
        while(low <= high)
        {
            int mid = (low+high)/2;
            if(nums[mid] < target)
                low = mid+1;
            else
                high = mid-1;
        }
        if(low == size)
            return result;
        //now we are sure high+1 is a valid index
        if(nums[high+1] != target) return result;
        
        //now we know (high+1) is left edge
        result[0] = high+1;
        
        low = high+1; high = size-1;
        while(low <= high) 
        { 
            int mid = (low+high)/2; if(nums[mid] > target)
                high = mid-1;
            else if(nums[mid] == target)
                low = mid+1;
            //no case that nums[mid] < target
        }
        result[1] = high; //or result[1] = low-1;
        return result;
    }
}

Python:

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        result = [-1]*2
        size = len(nums)
        if size == 0: return result
        low, high = 0, size-1
        while low <= high:
            mid = (low+high)/2
            if nums[mid] < target:
                low = mid+1
            else:
                high = mid-1;
        if low == size: return result
        if nums[high+1] != target: return result
        result[0] = high+1
        low, high = high+1, size-1
        while low <= high: 
            mid = (low+high)/2 
            if nums[mid] > target:
                high = mid-1
            else:
                low = mid+1
        result[1] = low-1
        return result