Skip to content

Latest commit

 

History

History
436 lines (396 loc) · 12.2 KB

二分查找.md

File metadata and controls

436 lines (396 loc) · 12.2 KB

二分查找解题步骤

  1. 确定二分左右边界
  2. 设计一个性质使得可以将区间划分成两段（要求的点在其中一段的端点）
  3. 区间更新

二分查找模板

bool check(int x) // 检查x是否满足某种性质
int bsearch_1(int l, int r){
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int bsearch_2(int l, int r){
    while (l < r){
        int mid = l + r + 1>> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

二分查找题型

leetcode.704 二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l < r){
            int mid = (l + r) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[l] == target) return l;
        return -1;
    }
};

leetcode.278 第一个错误的版本

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

class Solution {
public:
    int firstBadVersion(int n) {
        long l = 1, r = n;
        while (l < r){
            int mid = (l + r) / 2;
            if (isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return l;// 返回的是第一个错误的版本
    }
};

leetcode.35 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size();

        while (l < r){
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

leetcode.69 x的平方根

class Solution {
public:
    typedef unsigned long long ULL;
    int mySqrt(int x) {
        ULL l = 0, r = x;
        while (l < r){
            ULL mid = l + r + 1 >> 1;
            if (mid <= x / mid) l = mid;
            else r = mid - 1;
        }
        return l;
    }
};

leetcode.367 有效的完全平方数

  • 链接https://leetcode.cn/problems/valid-perfect-square/
  • 注意：与上一题区别在于只是判断是否存在完全平方数，不需要上取整或者下取整求完全平方数，所以使用模板一或者模板二均可
  • leetcode解题代码
class Solution {
public:
    typedef unsigned long long ULL;
    bool isPerfectSquare(int num) {
        ULL l = 1, r = num;
        while (l < r){
            ULL mid = l + r + 1>> 1;
            if (mid <= num / mid) l = mid;
            else r = mid - 1;
        }
        return l * l == num;
    }
};

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

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        int l = 0, r = nums.size() - 1;
        while (l < r){
            int mid = l + r >> 1;
            // 找到>=target的第一个数
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        if (nums[l] != target) return {-1, -1};
        int L = l;

        l = 0, r = nums.size() - 1;
        while (l < r){
            int mid = l + r + 1 >> 1;
            // 找到<=target的第一个数
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return {L, r};
    }
};

leetcode.74 搜索二维矩阵

  • 链接https://leetcode.cn/problems/search-a-2d-matrix/
  • 解题思路：将二维矩阵展成一维数组，二分
  • 注意：一维数组下标转换为矩阵下标
    行下标 = 数组下标 / 列数
    列下标 = 数组下标 % 列数
  • leetcode解题代码
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty()) return false;
        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n * m - 1;
        while (l < r){
            int mid = l + r >> 1;
            // 将矩阵下标转换为数组下标
            if (matrix[mid / m][mid % m] >= target) r = mid;
            else l = mid + 1;
        }

        if (matrix[l / m][l % m] == target) return true;
        return false;
    }
};

leetcode.153 寻找旋转排序数组中的最小值

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r){
            int mid = l + r >> 1;
            if (nums[mid] <= nums.back()) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};

leetcode.154 寻找旋转排序数组中的最小值II

class Solution {
public:
    int findMin(vector<int>& nums) {
        while (nums.size() > 1 && nums[0] == nums.back()) nums.pop_back();

        int l = 0, r = nums.size() - 1;
        while (l < r){
            int mid = l + r >> 1;
            if (nums[mid] <= nums.back()) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
};

leetcode.33 搜索旋转排序数组

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        // 找到最小值
        int l = 0, r = nums.size() - 1;
        while (l < r){
            int mid = (l + r) / 2;
            if (nums[mid] <= nums.back()) r = mid;
            else l = mid + 1;
        }
        // 判断目标值所在区间
        if (target <= nums.back()) r = nums.size() - 1;
        else l = 0, r --;
        // 在所在区间找目标值
        while (l < r){
            int mid = (l + r) / 2;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[l] == target) return l;
        return -1;
    }
};

下列题目没有二段性，但仍然可以通过二分每次缩小一半的搜索区间找到答案

leetcode.162 寻找峰值

  • 链接https://leetcode.cn/problems/find-peak-element/
  • 解题思路：如果二分的值比其右边的值小，那么说明当前是递增区间，那么右边一定存在峰值，同理，如果二分的中点的值比中点右边的值大，那么说明当前是递减区间，左边一定存在峰值
  • leetcode解题代码
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r){
            int mid = l + r >> 1;
            // 说明左边一定有峰值
            if (nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

leetcode.287 寻找重复数

  • 链接https://leetcode.cn/problems/find-the-duplicate-number/
  • 解题思路：抽屉原理，n+1 个苹果放进 n 个抽屉中必然有一个抽屉放了两个苹果，抽屉为数据范围 n，苹果为数字总数 n+1，对数据范围二分，记录二分中点左侧的数字总数，和左边数据范围对比，如果数字总数大于数据范围，说明重复数在左侧，右侧同理
  • leetcode解题代码
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r){
            int mid = l + r >> 1;

            int cnt = 0;
            for (auto c: nums){
                if (c >= l && c <= mid)
                    cnt ++;
            }
            if (cnt > mid - l + 1) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

Acwing.789 数的范围

给定一个按照升序排列的长度为 $n$ 的整数数组，以及 $q$ 个查询。

对于每个查询，返回一个元素 $k$ 的起始位置和终止位置（位置从 $0$ 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式
第一行包含整数 $n$ 和 $q$ ，表示数组长度和询问个数。

第二行包含 $n$ 个整数（均在 $1∼10000$ 范围内），表示完整数组。

接下来 $q$ 行，每行包含一个整数 $k$ ，表示一个询问元素。

输出格式
共 $q$ 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围
$1≤n≤100000$

$1≤q≤10000$

$1≤k≤10000$

输入样例：

6 3
1 2 2 3 3 4
3
4
5

输出样例：

3 4
5 5
-1 -1
  • 解题代码
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, q;
int a[N];

int main(){
    cin >> n >> q;
    
    for (int i = 0; i < n; i ++) cin >> a[i];
    
    while (q --){
        int x;
        cin >> x;
        
        int l = 0, r = n - 1;
        while (l < r){
            int mid = l + r >> 1;
            if (a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (a[l] != x) cout << "-1 -1" << endl;
        
        else {
            cout << l << ' ';
            
            l = 0, r = n - 1;
            while (l < r){
                int mid = l + r + 1 >> 1;
                if (a[mid] <= x) l = mid;
                else r = mid - 1;
            }
            
            cout << r << endl;
        }
    }
    return 0;
}

Acwing.790 数的三次方根

给定一个浮点数 $n$，求它的三次方根。

输入格式
共一行，包含一个浮点数 $n$。

输出格式
共一行，包含一个浮点数，表示问题的解。

注意，结果保留 $6$ 位小数。

数据范围
$−10000≤n≤10000$

输入样例：

1000.00

输出样例：

10.000000
  • 解题代码
#include <iostream>

using namespace std;

double n;

int main(){
    cin >> n;
    
    double l = -10000, r = 10000;
    while (r - l > 1e-8){
        double mid = (l + r) / 2;
        if (mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    printf("%.6f\n", l);
    return 0;
}