汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

二分查找以及多种变形

发表于 更新于 分类于 Valine：
本文字数： 7.9k 阅读时长 ≈ 7 分钟

原始题

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1  

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0){
            return -1;
        }
        int low = 0, high = n - 1;
        while (low <= high){
            int mid = low + (high - low) /2 ;
            if (nums[mid] == target){
                return mid;
            }else if(target > nums[mid]){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0 
        right = len(nums)-1
        while left <= right:
            mid = left + (right-left)//2
            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

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

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

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

进阶：

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

示例 1：

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

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

输入：nums = [], target = 0
输出：[-1,-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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int begin = -1, end = -1;
        if (n == 0){
            return vector<int>{begin,end};
        }
        int low = 0, high = n - 1;
        while (low <= high){
            int mid = low + (high - low) / 2;
            if (nums[mid] == target){
                begin = mid;
                end = mid;
                while (begin >= 0 && nums[begin] == target){
                    begin = begin - 1;
                }
                while (end < n && nums[end] == target){
                    end = end + 1;
                }
                return vector<int>{begin+1,end-1};
            }
            if (nums[mid] > target){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        return vector<int>{-1, -1};
    }
};

35. 搜索插入位置

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

请必须使用时间复杂度为 O(log n) 的算法。

 

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1
示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

寻找第一个大于等于目标值的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0){
            return 0;
        }
        int low = 0, high = n - 1;
        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if (nums[mid] >= target){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        // cout << low << " " << high << endl;
        // 最终low == high + 1
        return low;

    }
};

更清晰的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        // 查找第一个大于等于target值的位置
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target > nums[mid]) {
                left = mid + 1;
            }else if (target < nums[mid]) {
                right = mid - 1;
            }else{
                return mid;
            }
        }
        // 返回左边界
        return left;
    }
};

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

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

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

 
示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。
示例 2：

输入：n = 1, bad = 1
输出：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
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        if (n == 0){
            return 0;
        }
        int low = 0, high = n;
        while (low <= high){
            int mid = low + ((high-low) >> 1);
            if (isBadVersion(mid)){
                while (mid >=0 && isBadVersion(mid)){
                    mid = mid - 1;
                }
                return mid + 1;
            }else{
                low = mid + 1;
            }
        }
        cout << n << endl;
        return n;
        
    }
};

寻找第一个错误的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        if (n == 0){
            return 0;
        }
        int low = 1, high = n;
        while (low <= high){
            int mid = low + ((high-low) >> 1);
            if (isBadVersion(mid)){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        // 最终low = high + 1
        return high+1;
        
    }
};

374. 猜数字大小

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

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

 

示例 1：

输入：n = 10, pick = 6
输出：6
示例 2：

输入：n = 1, pick = 1
输出：1
示例 3：

输入：n = 2, pick = 1
输出：1
示例 4：

输入：n = 2, pick = 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
/** 
 * 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) {
        if (n == 1){
            return n;
        }
        int low = 1, high = n;
        while (low <= high){
            int mid = low + ((high-low) >> 1);
            int guess_tmp = guess(mid);
            if (guess_tmp == 0){
                return mid;
            }else if (guess_tmp == -1){
                high = mid - 1;
            }else{
                low = mid + 1;
            }
        }
        return n;
    }
};

658. 找到 K 个最接近的元素

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：

|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b  

示例 1：

输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]
示例 2：

输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]  

提示：

1 <= k <= arr.length
1 <= arr.length <= 104
arr 按 升序 排列
-104 <= arr[i], x <= 104

二分然后双指针
时间复杂度O(logn + k)

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
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n = arr.size();
        if (k <= 0){
            return vector<int>{};
        }
        if (n <= k){
            return arr;
        }
        if (x <= arr.front()){
            return vector<int>(arr.begin(), arr.begin()+k);
        }
        if (x >= arr.back()){
            return vector<int>(arr.end()-k, arr.end());
        }

        int low = 0, high = n - 1;
        while (low <= high){
            int mid = low + ((high - low) >> 1);
            if (x >= arr[mid]){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        // cout << low << endl;
        // 结果必然在[low-k-1, low+k-1]之间
        int begin = max(0, low-1-k);
        int end = min(low+k-1, n-1);
        while (end - begin + 1 > k){
            if (abs(arr[begin]-x) <= abs(arr[end]-x)){
                end--;
            }else{
                begin++;
            }
        }
        // cout << begin << " " << end << endl;
        return vector<int>(arr.begin()+begin, arr.begin()+end+1);

    }
};

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。

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

你可以假设 nums[-1] = nums[n] = -∞ 。

你必须实现时间复杂度为 O(log n) 的算法来解决此问题。

 

示例 1：

输入：nums = [1,2,3,1]
输出：2
解释：3 是峰值元素，你的函数应该返回其索引 2。
示例 2：

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5
解释：你的函数可以返回索引 1，其峰值元素为 2；
  或者返回索引 5， 其峰值元素为 6。

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
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();

        auto get = [&](int i) -> pair<int, int> {
            if (i == -1 || i == n) {
                return {0, 0};
            }
            return {1, nums[i]};
        };
        int low = 0, high = n-1;
        while (low <= high) {
            // cout << low << " " << high << endl;
            int mid = low + ((high-low) >> 1);
            if (get(mid-1) < get(mid) && get(mid) > get(mid+1)) {
                return mid;
            }
            if (get(mid) < get(mid+1)) {
                low = mid + 1;
            }else {
                high = mid - 1;
            }
        }
        return -1;
    }
};

852. 山脉数组的峰顶索引

符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。

 

示例 1：

输入：arr = [0,1,0]
输出：1
示例 2：

输入：arr = [0,2,1,0]
输出：1
示例 3：

输入：arr = [0,10,5,2]
输出：1
示例 4：

输入：arr = [3,4,5,1]
输出：2
示例 5：

输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2

此题与寻找峰值一题比较相似，但是此题只存在一个解。

上一题的答案可以直接用，并且可以无需考虑边界问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int peakIndexInMountainArray(vector<int>& nums) {
        int n = nums.size();
        int low = 1, high = n-2;
        while (low <= high) {
            // cout << low << " " << high << endl;
            int mid = low + ((high-low) >> 1);
            if (nums[mid] > nums[mid-1] && nums[mid] > nums[mid+1]) {
                return mid;
            }
            if (nums[mid] < nums[mid+1]) {
                low = mid + 1;
            }else {
                high = mid - 1;
            }
        }
        return -1;

    }
};
坚持原创分享，您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------