34 Find First and Last Position of Element in a Sorted Array

二分查找

Python

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

Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] range = new int[2];
        int left = 0;
        int right = nums.length;

        if (nums.length == 0)
            return new int[]{-1, -1};

        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] < target) left = mid + 1;
            else right = mid;
        }

        if (right >= nums.length || nums[right] != target)
            return new int[]{-1, -1};
        range[0] = right;
        right = nums.length;
        while(left < right){
            int mid = left + (right - left)/2;
            if(nums[mid] <= target)
                left = mid + 1;
            else
                right = mid;
        }
        range[1] = left - 1;
        return range;
    }
}