34. 在排序数组中查找元素的第一个和最后一个位置

问题

给定一个按照升序排列的整数数组 \(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]\)

解法

这个题乍一看就是二分查找的变种,考虑二分查找解决。
基本步骤如下:
使用二分法查找,假设\(start\)与\(end\)为数组起始位置与结束位置,有\(mid = (start + end)/2\)。此时,有三种情况会出现,我们首先排除掉\(nums[mid]!=target\)的两种情况:

  • 当\(nums[mid] < target\)时,\(start = mid + 1\);
  • 当\(nums[mid] > target\)时,\(end = mid - 1\);
    接下来,我们考虑当\(nums[mid] == target\)时的情况处理,此时,代表\(mid\)所在位置肯定是位于返回结果的中间,那么,起始位置要么就是\(mid\),要么肯定位于\(mid\)左侧,结束为止要么就是\(mid\),要没肯定位于\(mid\)右侧。
    继续使用二分法处理,但是与传统二分法不太一样的地方在于,各元素计算的方式有些不同,如果凭感觉写不出的话,可以在纸上写几个模拟数组试一下就行了。

    代码

    java 实现

    class Solution {
    public int[] searchRange(int[] nums, int target) {
    int start = 0, end = nums.length - 1;
    int[] result = new int[]{-1,-1};
    while (start <= end) {
    //首先需要二分法查询到nums[mid]==target的情况
    int mid = (start + end)/2;
    if (nums[mid] == target) {
    int temp = mid;
    while (start<mid) {
    int ml = (start+mid)/2;
    if (nums[ml] < target) {
    start = ml+1;
    } else {
    mid = ml;
    }
    }
    result[0] = start;
    mid = temp;
    while (mid < end) {
    int mr = (end + mid)/2 + 1;
    if (nums[mr] >target) {
    end = mr -1;
    } else {
    mid = mr;
    }
    }
    result[1] = end;
    return result;
    } else if (nums[mid] < target) {
    start = mid + 1;
    } else {
    end = mid - 1;
    }
    }
    return result;
    }
    }