leetcode34(在排序数组中查找元素的第一个和最后一个位置)Java语言实现

求：

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

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

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

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

 

题目链接： https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/

 

解：

1、线性查找

先从前往后遍历，得到target第一次出现的索引startIndex，如果target一次也没有出现过，返回{-1,-1}。再从后往前遍历，得到target最后一次出现的索引endIndex，最后返回索引对{startIndex,endIndex}。（如果事先知道重复的数量很少，第2趟可以接着上一次的遍历结果继续往后遍历，而如果重复的次数很多，从后往前遍历大概率会更好，这里我用从后往前做演示，时间复杂度来说2者是一样的），这个解法不符合题目时间复杂度为O(logN)的要求。

时间复杂度：O(N)

空间复杂度：O(1)

public int[] searchRange(int[] nums, int target) {
    int ret[] = {-1, -1};
    int N = nums.length;
    int i, j;
    for (i = 0; i ; i++) ;
    if (i == N) return ret;
    ret[0] = i;
    for (j = N - 1; j > i && nums[j] != target; j--) ;
    ret[1] = j;
    return ret;
}

2、二分查找+线性最大最小搜索

在排序数组中查找指定元素，并且要求时间复杂度是O(logN)，很自然的想到使用二分算法。在二分过程中，因为本题返回的是第一次和最后一次出现的索引对应的区间，因此如果出现了匹配，还需要分别向前和向后查找到不匹配为止，最后返回匹配区间。如果整个过程中都没有找到想要的元素，返回{-1，-1}。

网上很多人使用这种解法，但是这个解法依然不符合题目时间复杂度为O(logN)的要求。我们设想如果数组中的元素都是重复的，那么当使用二分找到target后，找target第一次和最后一次出现的索引所消耗的时间很明显是O(N)数量级，因此还需要继续优化。

时间复杂度：O(N)

空间复杂度：O(1)

public int[] searchRange(int[] nums, int target) {
    int ret[] = {-1, -1};
    int start = 0, end = nums.length - 1;
    while (start <= end) {
        int mid = (start + end) >> 1;
        if (nums[mid] == target) {
            int i = mid - 1, j = mid + 1;
            while (i >= 0 && nums[i] == nums[mid]) --i;
            while (j length && nums[j] == nums[mid]) ++j;
            ret[0] = i+1;
            ret[1] = j-1;
            break;
        } else if (nums[mid] 1;
        } else {
            end = mid - 1;
        }
    }
    return ret;
}

3、2趟二分搜索

使用2趟二分搜索，分别查找target第一次和最后一次出现的索引，因为每趟都是O(logN)数量级的操作，因此总的时间复杂度也是O(logN)数量级，符合题目要求。这里我们定义一个查找索引的函数searchIndex，它接受5个参数：数组nums、要查找的数target，起始查找索引start，终止查找索引end，以及一个标志位left。如果left是true，代表沿着左边找到最小索引。如果left是false，代表沿着右边找到最大索引。在主函数中2次调用searchIndex，得到起止位置，然后返回。

时间复杂度：O(logN)

空间复杂度：O(1)

public int[] searchRange(int[] nums, int target) {
    int ret[] = {-1, -1};
    int startIndex = searchIndex(nums, target, 0, nums.length - 1, true);
    if (startIndex == -1) return ret;
    ret[0] = startIndex;
    int endIndex = searchIndex(nums, target, startIndex, nums.length - 1, false);
    ret[1] = endIndex;
    return ret;
}

private int searchIndex(int[] nums, int target, int start, int end, boolean left) {
    int index = -1;
    while (start <= end) {
        int mid = (start + end) >> 1;
        if (nums[mid] == target) {
            index = mid;
            if (left) end = mid - 1;
            else start = mid + 1;
        } else if (nums[mid] 1;
        } else {
            end = mid - 1;
        }
    }
    return index;
}