Search for a Range

Problem: Search for a Range

I use one binary search to find the target and use two pointers to find the range. A faster way is to use two binary search to find the left and right boundaries.

Code in Python:

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)
        l, r = 0, n-1
        while l <= r:
            mid = (l+r)/2
            if nums[mid] == target:
                i = j = mid
                while i > 0 and nums[i-1] == nums[i]: i -= 1
                while j < n-1 and nums[j+1] == nums[j]: j += 1
                return [i, j]
            elif nums[mid] < target:
                l = mid+1
            else:
                r = mid-1
        return [-1, -1]

Code in Java:

public class Solution {
    public int[] searchRange(int[] nums, int target) {

        int[] res = {-1, -1};

        if (nums.length == 0 || nums == null) {
            return res;
        }

        int l = 0, r = nums.length;
        int m;
        while (l < r) {
            m = (l+r)/2;
            if (nums[l] == target && (l == 0 || nums[l-1] < nums[l])) {
                res[0] = l;
                break;
            }
            if (nums[m] < target) {
                if (l == m) break;
                l = m;
            }
            else if (nums[m] > target) r = m;
            else {
                if (m == 0 || nums[m-1] < nums[m]) {
                    res[0] = m;
                    break;
                } else {
                    r = m;
                }
            }
        }
        if (res[0] == -1) return res;

        l = res[0]; r = nums.length; m = (l+r)/2;
        while (l < r) {
            m = (l+r)/2;
            if (nums[l] == target && (l == nums.length-1 || nums[l+1] > nums[l])) {
                res[1] = l;
                break;
            }
            if (nums[m] > target) r = m;
            else {
                if (m == nums.length-1 || nums[m+1] > nums[m]) {
                    res[1] = m;
                    break;
                } else {
                    l = m;
                }
            }
        }
        return res;
    }
}