题目描述

Find First and Last Position of Element in Sorted Array

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

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

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

Input: nums = [2], target = 2
Output: [0, 0]

From leetcode No.34 Medium (opens new window)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        //code here
    }
}

解法

点击查看

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ret = {-1, -1};
        int left = findExtremeIndex(nums, target, true);
        if(left == nums.length || nums[left] != target){
            return ret;
        }
        ret[0] = left;
        ret[1] = findExtremeIndex(nums, target, false) - 1;
        return ret;

    }
    //find the leftmost or rightmost target index
    public int findExtremeIndex(int[] nums, int target, boolean isLeft){
        int left = 0;
        int right = nums.length;
        while(left < right){
            int mid = (left + right) / 2;
            if(isLeft){
                if(nums[mid] >= target){
                    right = mid;
                }else{
                    left = mid + 1;
                }
            }else{
                if(nums[mid] <= target){
                    left = mid + 1;
                }else{
                    right = mid;
                }
            }
        }
        return left;
    }
}

思考

我的自然想法：

• 二分法找到与 target相等的值，存在就再考虑向左右延申
  • 思想没有问题，只是特殊情况均要考虑到
    • 只有一个值相等的情况
    • 左右两个边界值
  • 总之不是很优雅

最优解

• 线性查找
  • 向从左到右依次轮询依次，确定第一个索引即退出
  • 如果一轮查找结束都没有匹配的值，说明不存在与target相等的值，直接退出
  • 如果确定了第一个索引值，那么再反向轮询一次，找到首个相等的值即为第二个索引
    • 第二个索引必定存在，最差的情况是与第一次查找的索引值相同
  • 实际上，因为数组是升序的，因此还可以进一步优化成一次循环就能得到结果
    点击查看

    class Solution {
        public int[] searchRange(int[] nums, int target) {
            final int[] ret = { -1, -1 };
            final int size = nums.length;
            for(int i=0; i<size; i++){
                if(nums[i] == target){
                    ret[0] = ret[1] = i;
                    int j = i + 1;
                    while(j < size){
                        if(nums[j] == nums[j-1]){
                            ret[1] = j;
                            j++;
                        }else{
                            break;
                        }
                    }
                    break;
                }
            }
            return ret;
        }
    };
    

满足本题要求，时间复杂度为 O(logn)的二分查找：

• 原理和线性查找很类似，只是把顺序迭代替换了二分查找，循环条件是left < right, 不再是找到即退出
  • 左边界(left)为0， 右边界(right)为数组长度值 nums.length， 中间值为 mid = (left + right) /2
  • 当 nums[mid] > target, 即目标值只可能在左半边区域，下次迭代时，令 right = mid
  • 当 nums[mid] < target, 即目标值只可能在右半边区域，下次迭代时，令 left = mid + 1
  • 当 nums[mid] == target时，即说明 target值存在，但此时不会立即退出
    • 如果要找最左边的索引，则规则与之前在左半边区域相同，即right = mid
    • 找最右边的索引，则往右半边区域继续二分即可
• 和线性查找的原理一样，先找最左边的的第一个索引
  • 那么迭代条件即为 nums[mid] >= target，满足条件执行 right = mid
  • 迭代结束时，结果有三种情况：
    1. 存在目标值， left(或 right)指向的值即为第一个索引值
    2. 不存在目标值， left指向的索引为第一个比 target值大的元素
    3. 不存在目标值， left指向的索引值为 nums.length(超出数组边界)
• 如果第一个索引没找到，即不存在目标值，也就不用找第二个了，如果存在，开始找第二个索引值
  • 再遍历一次，迭代条件为 nums[mid] <= target, 满足条件执行 left = mid + 1
  • 此时迭代结束，结果只有一种情况了，即 left指向的即为第二个索引值 + 1
  • 同理，因为数组有序的，找到最左边或最右边的索引后，可以直接左右延申找到第二个

总结

本题虽然最佳解法是线性遍历，但可作为二分法的最佳实践，总结二分法的几点规律

• 左边界(left)从 0开始没有问题， 右边界(right)为数组长度，而不是最后一个元素索引，确保可以迭代到所有元素。
• 循环控制条件为 left < right 或 left != right
• 中间值为 mid = (left + right) /2， 向下取整
• 当元素在左边范围时，下次迭代动作为 right = mid
• 当元素在右边范围时，下次迭代动作为 left = mid + 1
• 结束循环时会满足 left == right, left最小值为0，最大值为 right的初始值，也可能是中间值，会遍历到所有元素
• 当第一次遍历到与 target值相等的元素时，只是找到第一个这样的元素，并不是最左或最右的情况
• 如果要找 target出现在最右边的元素，则需要在找到目标元素后继续向右循环，退出时，right指向索引会刚好在最右 target索引右边一位
• 要找出现在最左边的元素，则需要在找到第一个目标元素后继续向左循环，退出时 left指向索引即为最左 target索引