二分查找：基础

睡不醒的鲤鱼 2021-05-15 每日一题 LeetCode

# 0034. 在排序数组中查找元素的第一个和最后一个位置 (opens new window)

题目

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

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

解析

求左右边界的二分查找。

二分算法，见算法模板：整数二分。

代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};

        vector<int> ans(2);

        // 找到左端点（第一个 >= target 的元素下标）
        // 左侧：nums[i] < target
        // 右侧：nums[i] >= target
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[l] != target) return {-1, -1};
        ans[0] = l;

        // 找到右端点（最后一个 >= target 的元素下标）
        // 左侧：nums[i] <= target
        // 右侧：nums[i] > target
        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2 + 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        ans[1] = r;

        return ans;
    }
};

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

# 0035. 搜索插入位置 (opens new window)

题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

解析

基础二分查找。

二分算法，见算法模板：整数二分。

代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 找到第一个 >= target 的元素下标
        // 左侧：nums[i] < target
        // 右侧：nums[i] >= target
        int l = 0, r = nums.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 0069. x 的平方根 (opens new window)

题目

实现 int sqrt(int x) 函数。

解析

二分算法，见算法模板：整数二分。

代码

class Solution {
public:
    int mySqrt(int x) {
        // 找到 x 的平方根（左侧最后一个下标）
        // 左侧：nums[i]^2 <= x
        // 右侧：nums[i]^2 > x
        int l = 0, r = x;
        while (l < r) {
            int mid = l + (r - l) / 2 + 1;
            if (mid <= x / mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 0162. 寻找峰值 (opens new window)

题目

给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

解析

二分查找条件：

$nums[mid] > nums[mid + 1]$ ：处于下坡，缩小至左侧闭区间；
$nums[mid] \leq nums[mid + 1]$ ：处于上坡，缩小至右侧开区间。

代码

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 0275. H 指数 II (opens new window)

题目

给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照升序排列。编写一个方法，计算出研究者的 h 指数。

解析

求左边界的二分查找。

代码

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (citations[mid] > n - mid) {
                right = mid - 1;
            } else if (citations[mid] < n - mid) {
                left = mid + 1;
            } else if (citations[mid] == n - mid) {
                right = mid - 1;
            }
        }
        return n - left;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 0278. 第一个错误的版本 (opens new window)

题目

假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

解析

二分查找条件：

isBadVersion(mid)：可能是第一个错误版本，缩小至左侧闭区间；
!isBadVersion(mid)：缩小至右侧开区间。

代码

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 0349. 两个数组的交集 (opens new window)

题目

给定两个数组，编写一个函数来计算它们的交集。

解析

对一个数组进行排序后，遍历另一个数组，通过二分查找判断元素是否同时存在于两个数组。

代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums2.begin(), nums2.end());
        set<int> setRet;
        for (int i = 0; i < nums1.size(); i ++) {
            if (binarySearch(nums2, nums1[i])) {
                setRet.insert(nums1[i]);
            }
        }
        vector<int> ans;
        ans.assign(setRet.begin(), setRet.end());
        return ans;
    }

    bool binarySearch(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

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

# 0350. 两个数组的交集 II (opens new window)

题目

给定两个数组，编写一个函数来计算它们的交集。

说明：输出结果中每个元素出现的次数，应与元素在两个数组中出现次数的最小值一致。

解析

使用 map 记录 nums1 中每个元素出现次数，遍历 nums2，每遇到一个重复元素则更新 map 值，最终得到交集。

代码

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> cnt;
        for (int i = 0; i < nums1.size(); i ++) {
            cnt[nums1[i]] ++;
        }
        vector<int> ans;
        for (int i = 0; i < nums2.size(); i ++) {
            if (cnt[nums2[i]]-- > 0) {
                ans.push_back(nums2[i]);
            }
        }
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 0374. 猜数字大小 (opens new window)

题目

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num

返回我选出的数字。

解析

基础二分查找。

代码

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

class Solution {
public:
    int guessNumber(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            int ret = guess(mid);
            if (ret == -1) {
                right = mid - 1;
            } else if (ret == 1) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }
};

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

# 0540. 有序数组中的单一元素 (opens new window)

题目

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

解析

二分查找条件（定义 i 为偶数）：

$nums[i] = nums[i + 1]$ ，缩小至右侧开区间；
$nums[i] != nums[i + 1]$ ，缩小至左侧闭区间。

代码

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mid % 2 == 1) --mid;
            if (nums[mid] == nums[mid + 1]) {
                left = mid + 2;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

数组：其他二分查找：旋转

鲤鱼笔记

Choose mode