Grizzly's daily
0%

数组解题技巧3——二分查找

发表于 分类于
本文字数： 3k 阅读时长 ≈ 3 分钟

本文是关于问题有序数组的二分查找问题，1.查找一个元素；2.查找区间全元素。

涉及 leetcode 的704. 二分查找和34. 在排序数组中查找元素的第一个和最后一个位置。

二分查找

题目1

首先来看题目704. 二分查找：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例1：

输入：nums = [-1,0,3,5,9,12], target = 9

输出：4

示例2：

输入：nums = [-1,0,3,5,9,12], target = 2

输出：-1

理解一下1

题目的大概意思就是：在有序数组nums中找出与target相同的元素的索引位置。

直接遍历的时间复杂度是O(n)，而这里是有序数组，那么就可以使用二分查找，由此时间复杂度为O(log n)。

基本的思路是：

  1. 约束查找区间左索引指针left和右索引指针right，获得中间索引指针mid；
  2. 判断mid指向的元素与target的大小：
    1. 等于target：返回该mid索引；
    2. 大于target：说明在左侧，right向左收缩；
    3. 小于target：说明在右侧，left向右收缩；

解题1

需要注意的是right和left是闭区间，并且while循环中使用的是\(\leq\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1; // 右侧需要减一
    // 计算 mid 时需要防止太大溢出
    int mid = left + (right-left)/2;
    while(left <= right){
        if(nums[mid] == target){
            return mid;
        }
        else if(nums[mid] > target){
            right = mid - 1;
        }
        else if(nums[mid] < target){
            left = mid +1;
        }
        mid = left + (right-left)/2;
    }
    return -1;
}

查找元素区间

题目2

首先来看题目34. 在排序数组中查找元素的第一个和最后一个位置：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回[-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]

理解一下2

这道题目是想要寻找等于target的所有元素，由于是有序数组，所以由一个区间表示。主要的问题在于如何寻找到区间的左右边界。

这里有两个思路，都是利用二分查找。

解题2.1

  1. 按照普通的二分查找，找到寻找一个等于target的元素位置；
  2. 若未找到则flag置为false；
  3. 若找到了，那么向左右依次寻找临界点即可。
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
vector<int> searchRange(vector<int>& nums, int target) {
    int left = 0, right = nums.size()-1;
    int mid = left + (right-left)/2;
    bool flag = false;
    while(left <= right){
        if(nums[mid] == target){  // 此处判断元素相等则跳出循环
            flag = true;
            break;
        }
        else if(nums[mid] > target){
            right = mid - 1;
        }
        else if(nums[mid] < target){
            left = mid + 1;
        }
        mid = left + (right-left)/2;
    }
    if(flag){
        left = mid;
        right = mid;
        while(--left >= 0 && nums[left] == target);
        while(++right < nums.size() && nums[right] == target);
        return {++left, --right};
    }
    return {-1,-1};
}

题解2.2

与方法一不同，直接去寻找左右端点。

需要修改的地方仅仅是在二分查找相等时和收缩边界的情况统一起来，如下：

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
vector<int> searchRange(vector<int>& nums, int target) {
    int left = leftRange(nums, target);
    if(left == -1){
        return {-1, -1};
    }
    int right = rightRange(nums, target);
    return {left, right};
}

int leftRange(vector<int>& nums, int target){
    int left = 0, right = nums.size()-1;
    int mid = left + (right-left)/2;
    while(left <= right){
        if(nums[mid] < target){
            left = mid + 1;
        }
        else{
            right = mid - 1;  // 右侧向左侧收缩，找到左端点
        }
        mid = left + (right-left)/2;
    }
    if(left >= nums.size() || nums[left] != target){
        return -1;
    }
    return left;
}

int rightRange(vector<int>& nums, int target){
    int left = 0, right = nums.size()-1;
    int mid = left + (right-left)/2;
    while(left <= right){
        if(nums[mid] > target){
            right = mid - 1;
        }
        else{
            left = mid + 1;  // 左侧向右侧收缩，找到右端点
        }
        mid = left + (right-left)/2;
    }
    if(right < 0 || nums[right] != target){
        return -1;
    }
    return right;
}

个人收获

这里使用的二分查找比较简单，类似于一棵树，主要就是收缩区间和循环终止等一些细节问题。

第二个关于区间问题的方法，在leetcode上虽然第一个方法的效率较高，但是第二个方法的模块化和层次化要更好，更适合进行改编改写。

------ 本文结束------