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

Leetcode Array Binary Search

Given an array of integers nums sorted in ascending order, 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 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Python

在排序数组中查找元素的第一个和最后一个位置。由于数组是排序的，而且时间复杂度要求是$O(\log n)$，最典型的就是二分查找了。最直接的方法是通过二分查找方法找到目标值所在的位置$k$，即nums[k] = target，然后从$k$开始向左右扫描来定位左右边界。

Java

public int[] searchRange(int[] nums, int target) {
    if (nums == null || nums.length == 0) return new int[]{-1, -1};
    int n = nums.length;
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo)/2;
        int cmp = nums[mid] - target;
        if (cmp > 0) hi = mid - 1;
        else if (cmp < 0) lo = mid + 1;
        else {
            lo = mid; hi = mid;
            while (lo >=0  && nums[lo] == nums[mid]) lo--;
            while (hi < n  && nums[hi] == nums[mid]) hi++;
            return new int[]{lo + 1, hi - 1};
        }
    }
    return new int[]{-1, -1};
}

Python

def searchRange(self, nums, target):
    n = len(nums) 
    left = 0
    right = n - 1

    result_left, result_right = -1, -1
    while left <= right：
        mid = (left + right) //2
        print(left, right, mid)

        if nums[mid] == target:   
            tmp = mid
            while tmp > -1 and nums[tmp] == target:
                tmp -= 1
            result_left = tmp+1
            tmp = mid
            while tmp < n and nums[tmp] == target:
                tmp += 1
            result_right = tmp-1
            return [result_left, result_right]
        elif nums[mid] > target:
            right = mid - 1
        else:
            left = mid + 1   
    return [-1, -1]    

二分查找的时间复杂度是$O(\log n)$，查找左右边界的时间复杂度是$O(k)$，其中$k$是边界的长度。当所有元素的值都为目标值时，最坏时间复杂度是$O(n)$。不符合题目的时间复杂度要求。

一个更优化的方案是，在寻找左右边界时也采用二分查找的办法，具体方法是：先找到该值的位置find, 针对左边界，寻找[0, find]的区间，针对右边界，寻找[find, nums.length-1]区间，直到区间内找不到该值。

binarySearch()方法使用二分查找算法查找区间内的目标值，如果查找到该值，则返回该值的位置；如果没有查找到该值，则返回小于该值的位置。

另外，特别需要注意程序中下标的溢出。

public int[] searchRange(int[] nums, int target) {        
    // starting and ending position of a given target value.
    int left, right;
    // 查找目标值
    int find = binarySearch(nums, 0, nums.length - 1, target);
    // 没有查找到目标值
    if (find < 0 || nums[find] != target) return new int[]{-1, -1};
    // 向左搜索目标值
    int findLeft = find;
    while (findLeft != 0 && nums[findLeft] == target)
         findLeft = binarySearch(nums, 0, findLeft - 1, target);
    if (nums[findLeft] == target) left = findLeft;
    else left = findLeft + 1;
    // 向右搜索目标值
    int findRight = find;
    while (findRight != nums.length - 1 &&  nums[findRight] == target) {
        int findRightRes = binarySearch(nums, findRight + 1, nums.length - 1, target);
        if (findRightRes < findRight + 1) break;
        findRight = findRightRes;
    }
    if (nums[findRight] == target) right = findRight;
    else right = findRight - 1;
    return new int[]{left, right};
}

// find the index of target.
private int binarySearch(int[] nums, int lo, int hi, int target) {
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        int cmp = nums[mid] - target;
        if (cmp > 0)        hi = mid - 1;
        else if (cmp < 0)   lo = mid + 1;
        else                return mid;
    }
    return lo - 1;
}

有没有更好的办法呢？使用一个trick: 为了查找右边界，可以查找比目标值大一点点的值；为了查找左边界，可以查找比目标值小一点点的值。

public int[] searchRange(int[] nums, int target) {        
    double left = target - 0.5, right = target + 0.5;
    int l = binarySearch(nums, left);
    int r = binarySearch(nums, right);
    if(l == r) return new int[]{-1, -1};
    return new int[]{l, r - 1};
}

public int binarySearch(int[] nums, double target) {
    int lo = 0, hi = nums.length - 1;
    while(lo <= hi){
        int mid = lo + (hi - lo)/2;
        if(target > nums[mid]) lo = mid + 1;
        else hi = mid - 1;
    }
    return lo;
}