题目描述

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

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

进阶：

  • 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1： 

1
2
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2： 

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

示例 3： 

1
2
输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • nums 是一个非递减数组
  • -10^9 <= target <= 10^9

解法

  • 两次二分查找
    • 第一次查找最左边的元素
    • 第二次查找最右边的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n=nums.length;
        int result[]={-1,-1};
        //特殊情况处理
        if (n==0){
            return  result;
        }
        int firstPosition=findFirstPosition(nums,target);
        //如果第一个元素没有找到，说明没有这个元素 直接返回
        if (firstPosition==-1){
            return result;
        }
        int lastPosition=findLastPosition(nums,target);
        result[0]=firstPosition;
        result[1]=lastPosition;
        return result;
    }

    private int findFirstPosition(int[] nums, int target) {
        //这个方法可以看做是找target 但是找到是最左边的数
        int left=0;
        int right=nums.length-1;
        while (left<right){
            int mid=(left+right)/2;
            //1.mid及其左边的元素都不符合
            if (nums[mid]<target){
                left=mid+1;
            }
            //2.mid右边的元素肯定不是第一个出现的mid！
            //这里虽然找到了目标值，但是不知道是不是最左边的，保险起见让它为右边界继续找
            else if (nums[mid]==target){
                right=mid;
            }
            else {
                //num[mid]>target ，mid及其右边的元素肯定不是
                right=mid-1;
            }
        }
        //最后看有没有找到目标值
        if (nums[left]==target){
            return left;
        }
        return -1;
    }

    private int findLastPosition(int[] nums, int target) {
        //这个方法可以看做是找target 但是找到是最右边的数
        int left=0;
        int right=nums.length-1;
        while (left<right){
            int mid=(left+right+1)/2;
            //这里要注意要向上取整，因为有left=mid和left=mid+1，可能会导致死循环
            //1.mid及其左边的元素都不符合
            if (nums[mid]<target){
                //下一轮为[mid+1,right]
                left=mid+1;
            }
            //2.mid左边的元素肯定不是最后一个出现的mid！
            //类比同上
            else if (nums[mid]==target){
                //下一轮为[mid,right]
                left=mid;
            }
            else {
                //num[mid]>target ，mid及其右边的元素肯定不是
                //下一轮为[left,mid-1]
                right=mid-1;
            }
        }
        //最后看有没有找到目标值
        //这里其实已经没有必要找了因为firstPosition已经判断过了
        //不过可以作为一个单独的函数来看，就把条件加上了
        if (nums[left]==target){
            return left;
        }
        return -1;
    }
}
  • 时间复杂度：O(logn)

来源：力扣（LeetCode）
链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

总结

二分查找可以分为以下三类

  • 只找目标值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int search(int[] nums, int target) {
        int left;
        int right;
        while (left<right){
            //[l,r]->[l,m]&&[m+1,r]
            int mid=(left+right)/2;
            if (nums[mid]==target){
                return target;
            }
            else if (nums[mid]<target){
                left=mid+1;
            }else if (nums[mid]>target){
                right=mid;
            }
        }
    }
  • 找第一个目标值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
private int findFirstPosition(int[] nums, int target) {
       //这个方法可以看做是找target 但是找到是最左边的数
       int left=0;
       int right=nums.length-1;
       while (left<right){
           int mid=(left+right)/2;
           //1.mid及其左边的元素都不符合
           if (nums[mid]<target){
               left=mid+1;
           }
           //2.mid右边的元素肯定不是第一个出现的mid！
           //这里虽然找到了目标值，但是不知道是不是最左边的，保险起见让它为右边界继续找
           else if (nums[mid]==target){
               right=mid;
           }
           else {
               //num[mid]>target ，mid及其右边的元素肯定不是
               right=mid-1;
           }
       }
       //最后看有没有找到目标值
       if (nums[left]==target){
           return left;
       }
       return -1;
   }
  • 找最后一个目标值
    • 注意是否会导致死循环要向上取整
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
private int findLastPosition(int[] nums, int target) {
        //这个方法可以看做是找target 但是找到是最右边的数
        int left=0;
        int right=nums.length-1;
        while (left<right){
            int mid=(left+right+1)/2;
            //这里要注意要向上取整，因为有left=mid和left=mid+1，可能会导致死循环
            //1.mid及其左边的元素都不符合
            if (nums[mid]<target){
                //下一轮为[mid+1,right]
                left=mid+1;
            }
            //2.mid左边的元素肯定不是最后一个出现的mid！
            //类比同上
            else if (nums[mid]==target){
                //下一轮为[mid,right]
                left=mid;
            }
            else {
                //num[mid]>target ，mid及其右边的元素肯定不是
                //下一轮为[left,mid-1]
                right=mid-1;
            }
        }
        //最后看有没有找到目标值
        //这里其实已经没有必要找了因为firstPosition已经判断过了
        //不过可以作为一个单独的函数来看，就把条件加上了
        if (nums[left]==target){
            return left;
        }
        return -1;
    }