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

title	toc	date	tags	top
34. Find First and Last Position of Element in Sorted Array	false	2017-10-30	Leetcode Array Binary Search	34

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$开始向左右扫描来定位左右边界。

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};
}

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;
}