算法题421：在排序数组中查找元素的第一个和最后一个位置-对二分法查找的改造

（给算法爱好者加星标，修炼编程内功）

来源： 数据结构和算法-山大王wld

问题描述

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

二分法查找

题中说了是升序的数组，也就是排过序的，对于排过序的数组查找我们

很容易想到的就是二分法。这里要返回的是目标值在数组中的开始位置和结束位置，因为相同的数字在排序数组中肯定是挨着的，所以我们通过二分法查到之后，还要往前和往后继续查找，直到不等于目标值为止。

如果是做Android的并且经常看源码的可能知道，Android中有个类ArrayMap，他存储的时候hash值是排过序的，查找的时候也是通过二分法查找，但有可能hash值会有冲突，所以他查找之后也是分别往前和往后继续查找然后再比较key值，和这题解法很相似。我们来画个简图看一下

比如我们通过二分法查找7，然后还要往他的前面和后面继续查找，目的是要找到最开始7和最后7的位置，来看下代码

 1public int[] searchRange(int[] nums, int target) {
 2    int find = searchRangeHelper(nums, target);
 3    //如果没找到，返回{-1, -1}
 4    if (find == -1)
 5        return new int[]{-1, -1};
 6    int left = find - 1;
 7    int right = find + 1;
 8    //查看前面是否还有target
 9    while (left >= 0 && nums[left] == target)
10        left--;
11    //查看后面是否还有target
12    while (right < nums.length && nums[right] == target)
13        right++;
14    return new int[]{left + 1, right - 1};
15}
16
17//二分法查找
18public int searchRangeHelper(int[] nums, int target) {
19    int low = 0;
20    int high = nums.length - 1;
21    while (low <= high) {
22        int mid = low + (high - low) / 2;
23        int midVal = nums[mid];
24        if (midVal < target) {
25            low = mid + 1;
26        } else if (midVal > target) {
27            high = mid - 1;
28        } else {
29            return mid;
30        }
31    }
32    return -1;
33}

二分法的另一种写法

二分查找一般我们找到某个值之后会直接返回。其实我们有时候还可以对二分法进行改造，当查找某个值的时候不直接返回，而是要继续查找，直到左右两个指针相遇为止。像下面这样，代码中有详细的注释，可以看一下

 1public int[] searchRange(int[] nums, int target) {
 2    //查找第一个出现的target
 3    int first = searchRangeHelper(nums, target);
 4    //判断有没有查找到
 5    if (first < nums.length && nums[first] == target) {
 6        //如果查找到了，说明有这个值，我们再来查(target + 1)，如果有这个值，
 7        //那么查找的结果也是第一次出现的(target + 1)的下标，我们减去1，就是target
 8        //最后一次出现的下标。如果没有(target + 1)这个值，那么查找的结果就是第一个
 9        // 大于target的下标，我们减去1也是target最后一次出现的下标。所以这里
10        // 无论有没有(target + 1)这个值，都不影响
11        int last = searchRangeHelper(nums, target + 1) - 1;
12        return new int[]{first, last};
13    } else {
14        //没有找到这个值，直接返回{-1, -1}
15        return new int[]{-1, -1};
16    }
17}
18
19//如果数组nums中有多个target，那么返回值就是第一个出现的target的下标
20//如果数组nums中没有target，那么返回的就是第一个大于target的下标
21public static int searchRangeHelper(int[] nums, double target) {
22    int low = 0, high = nums.length - 1;
23    while (low <= high) {
24        int m = low + (high - low) / 2;
25        if (target > nums[m])
26            low = m + 1;
27        else
28            high = m - 1;
29    }
30    return low;
31}

看到这里可能有的同学灵光乍现，通过二分法能找到target第一次出现的位置，那么通过二分法能不能找到target最后一次出现的位置。当然也是可以的，代码在下面给你准备好了

 1public int[] searchRange(int[] nums, int target) {
 2    int first = searchFirst(nums, target);
 3    //判断有没有查找到
 4    if (first < nums.length && nums[first] == target) {
 5        int last = searchLast(nums, target);
 6        return new int[]{first, last};
 7    } else {
 8        //没有找到这个值，直接返回{-1, -1}
 9        return new int[]{-1, -1};
10    }
11}
12
13//如果数组nums中有多个target，那么返回值就是第一个出现的target的下标
14//如果数组nums中没有target，那么返回的就是第一个大于target的下标
15public static int searchFirst(int[] nums, double target) {
16    int low = 0, high = nums.length - 1;
17    while (low <= high) {
18        int m = low + (high - low) / 2;
19        if (target > nums[m])
20            low = m + 1;
21        else
22            high = m - 1;
23    }
24    return low;
25}
26
27public static int searchLast(int[] nums, double target) {
28    int low = 0, high = nums.length - 1;
29    while (low <= high) {
30        int m = low + (high - low) / 2;
31        if (target >= nums[m])
32            low = m + 1;
33        else
34            high = m - 1;
35    }
36    return high;
37}

总结

以前对二分法的查找，我们是找到之后就返回。但如果有多个重复的值，我们是没法确定返回的是哪个值的下标。今天这里我们对二分法进行了改造，如果有多个重复的值，你想返回第一个值或者最后一个值的下标都是可以的。

- EOF -

推荐阅读  点击标题可跳转

觉得本文有帮助？请分享给更多人

关注「算法爱好者」加星标，修炼编程内功

好文章，我在看❤️