【二分查找】【浮点数的二分查找】【二分答案查找】

文章目录

前言
一、二分查找（Binary Search）
二、浮点数的二分查找
三、二分答案
总结

前言

今天记录一下基础算法之二分查找

一、二分查找（Binary Search）

二分查找（Binary Search）是一种在有序数组中查找目标值的算法。它的原理是通过将数组分成两半并检查目标值是否在数组的中间，从而不断缩小搜索范围，直到找到目标值或确定目标值不存在为止

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果目标值在中间，则返回
        if (arr[mid] == target)
            return mid;
        // 如果目标值比中间值小，则在左半部分继续搜索
        else if (arr[mid] > target)
            right = mid - 1;
        // 如果目标值比中间值大，则在右半部分继续搜索
        else
            left = mid + 1;
    }

    // 如果未找到目标值，则返回 -1
    return -1;
}

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17};
    int target = 11;
    int result = binarySearch(arr, target);
    if (result != -1)
        std::cout << "目标值 " << target << " 在索引 " << result << " 处找到。" << std::endl;
    else
        std::cout << "目标值 " << target << " 未找到。" << std::endl;

    return 0;
}

二、浮点数的二分查找

浮点数的二分查找与整数的二分查找非常相似，但需要处理浮点数比较时可能出现的精度问题。

#include <iostream>
#include <vector>
#include <cmath>

// 定义一个足够小的值，用于比较浮点数的精度
const double EPSILON = 1e-9;

int binarySearch(const std::vector<double>& arr, double target) {
    int left = 0;
    int right = arr.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        // 如果目标值在中间，则返回
        if (std::abs(arr[mid] - target) < EPSILON)
            return mid;
        // 如果目标值比中间值小，则在左半部分继续搜索
        else if (arr[mid] > target)
            right = mid - 1;
        // 如果目标值比中间值大，则在右半部分继续搜索
        else
            left = mid + 1;
    }

    // 如果未找到目标值，则返回 -1
    return -1;
}

int main() {
    std::vector<double> arr = {1.0, 3.2, 5.5, 7.7, 9.8, 11.0, 13.3, 15.5, 17.6};
    double target = 11.0;
    int result = binarySearch(arr, target);
    if (result != -1)
        std::cout << "目标值 " << target << " 在索引 " << result << " 处找到。" << std::endl;
    else
        std::cout << "目标值 " << target << " 未找到。" << std::endl;

    return 0;
}

三、二分答案

二分答案（Binary Search for Answer）是一种解决优化问题的常见方法，其中问题的解是一个实数或整数，并且有一个单调函数关系。在这种情况下，我们可以使用二分查找来快速找到满足特定条件的最优解。
check 函数用于检查是否满足条件，binarySearch 函数使用二分搜索来找到满足条件的最小值。

#include <iostream>
#include <functional>

using namespace std;

// 二分答案
double binary_search_answer(double left, double right, function<bool(double)> predicate) {
    const double EPSILON = 1e-9; // 精度控制

    while (right - left > EPSILON) {
        double mid = left + (right - left) / 2;
        if (predicate(mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }

    return left;
}

// 检查函数：判断 x 是否大于 5
bool check(double x) {
    return x > 5;
}

int main() {
    // 在区间 [0, 10] 中找到满足 is_greater_than_five 的最小值
    double result = binary_search_answer(0, 10, check);
    cout << "满足条件的最小值为: " << result << endl;

    return 0;
}

正好小唐在昨天写小白赛题目的时候遇到了一个题用到了二分答案,正好当成例题如下:
在这里插入图片描述

这个思路就是找到一个最小正整数x,是个查找问题,查找的规律满足是一个算术不等式,并且该算术不等式满足函数的单调性,那么我们就可以使用二分答案去解决这个问题,cheak函数为满足算术不等式,查找范围为1到一个很大的数。那么我们就可以写出如下代码:

#include <iostream>
#include <cmath>

using namespace std;

bool check(int x, int k, int m) {
    return sqrt(x) + floor(log(x) / log(k)) - m > 0;
}

int binary_search(int k, int m) {
    int left = 1;
	long long right = 10000000000LL; // 根据题目要求设定搜索范围

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (check(mid, k, m)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

int main() {
  int t;
  cin >> t;
	
	int k[t][2];
  for (int i = 0; i < t ; ++i) {
    cin >> k[i][0] >> k[i][1]; 
	}
	
  for (int i = 0; i < t; ++i) {

      cout << binary_search(k[i][0], k[i][1]) << endl;
  }

    return 0;
}