详解C语言中二分查找的运用技巧

目录
  • 基础的二分查
    • 查找左侧边界
    • 查找右侧边界
  • 二分查找问题分析
  • 实例1: 爱吃香蕉的珂珂
  • 实例2:运送包裹

前篇文章聊到了二分查找的基础以及细节的处理问题,主要介绍了 查找和目标值相等的元素、查找第一个和目标值相等的元素、查找最后一个和目标值相等的元素 三种情况。

这些情况都适用于有序数组中查找指定元素 这个基本的场景,但实际应用中可能不会这么直接,甚至看了题目之后,都不会想到可以用二分查找算法来解决 。

本文就来分析下二分查找在实际中的应用,通过分析几个应用二分查找的实例,总结下能使用二分查找算法的一些共同点,以后大家遇到相关的实际问题时,能有一个基本的分析方法,不至于一点儿头绪也没有 。

基础的二分查

找先来回顾下基础的二分查找的基本框架,一般实际场景都是查找和 target 相等的最左侧的元素或者最右侧的元素,代码如下:

查找左侧边界

int binary_search_firstequal(vector<int> &vec, int target)
{
    int ilen = (int)vec.size();
    if(ilen <= 0) return -1;
    int left = 0;
    int right = ilen - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        //找到了目标,继续向左查找目标
        if (target == vec[mid]) right = mid - 1;
        else if(target < vec[mid]) right = mid -1;
        else left = mid + 1;
    }
    if(right + 1 < ilen && vec[right + 1] == target) return right+1;
    return -1;
}

查找右侧边界

int binary_search_lastequal(vector<int> &vec, int target)
{
    int ilen = (int)vec.size();
    if(ilen <= 0) return -1;
    int left = 0;
    int right = ilen - 1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        //找到了目标,继续向右查找目标
        if (target == vec[mid]) left = mid + 1;
        else if(target < vec[mid]) right = mid -1;
        else left = mid + 1;
    }
    if(left - 1 < ilen && vec[left - 1] == target) return left - 1;
    return -1;
}

二分查找问题分析

二分查找问题的关键是找到一个单调关系,单调递增或者单调递减。

我们把二分查找的代码简化下:

int target;             // 要查找的目标值
vector<int> vec;        // 数组
int left = 0;           // 数组起始索引
int right = ilen - 1;   // 数组结束索引
while (left <= right)   // 查找 target 位于数组中的索引
{
   int mid = left + (right - left) / 2;
   if (target == vec[mid]) return mid;
}

上面的二分查找的单调关系是什么呢 ?是数组的索引和索引处元素的值,索引越大,元素的值越大,用伪代码表示形式如下:

int func(vector<int>&vec,int index)
{
    return vec[index];
}
int search(vector<int>&vec,int target)
{
  while (left <= right)
  {
     int mid = left + (right - left) / 2;
     if (target == func(vec,mid))
     {
         ....
     }
     else if(target > func(vec,mid))
     {
         ...
     }
     else
     {
         ...
     }
  }
}

上述伪代码中,我们把单调关系用一个函数 func 来表示,传入参数是数组以及数组索引,函数返回数组指定索引处的元素。

在二分查找的 while 循环中 target 直接和 func 函数的返回值进行比较。

听起来有些抽象,我们直接从 leetcode 上选几道题来分析下。

实例1: 爱吃香蕉的珂珂

从题目的描述,跟有序数组完全不搭边,所以初看这道题,根本想不到用二分查找的方法去分析 。

如果看完题目,没有任何思路的话,可以缕一缕题目涉及到的条件,看能否分析出一些有用的点 。

  • 题意分析
  • 珂珂要吃香蕉,面前摆了 N 堆,一堆一堆地吃
  • 珂珂 1 小时能吃 K 根,但如果一堆少于 K 根,那也得花一小时
  • 如果 1 堆大于 K 根,那么超过 K 的部分也算 1 小时
  • 问:只给 H 小时,珂珂要吃多慢(K 多小),才能充分占用这 H 小时

一般题目的问题是什么,单调关系就跟什么有关,根据题意可知:珂珂吃香蕉的速度越小,耗时越多。反之,速度越大,耗时越少,这就是题目的 单调关系 。

我们要找的是速度, 因为题目限制了珂珂一个小时之内只能选择一堆香蕉吃,因此速度最大值就是这几堆香蕉中,数量最多的那一堆, 最小速度毫无疑问是 1 了,最大速度可以通过轮询数组获得 。

int maxspeed = 1;
for(auto &elem : vec)
{
    if(elem > maxspeed) maxspeed = elem;
}+

又因为珂珂一个小时之内只能选择一堆香蕉吃,因此,每堆香蕉吃完的耗时 = 这堆香蕉的数量 / 珂珂一小时吃香蕉的数量。根据题意,这里的 / 在不能整除的时候,还需要花费 1 小时吃完剩下的,所以吃完一堆香蕉花费的时间,可以表示成 。

hour = piles[i] / speed;
if(0 != piles[i] % speed) hour += 1;

香蕉的堆数以及每堆的数量是确定的,要在 H 小时内吃完,时间是输入参数,也是确定的了,现在唯一不确定的就是吃香蕉的速度,我们需要做的就是在最小速度 到 最大速度之间找出一个速度,使得刚好能在 H 小时内吃完香蕉 。

前面说到吃香蕉的速度和吃完香蕉需要的时间之间是单调关系,我们先把单调关系的函数定义出来 。

// 速度为 speed 时,吃完所有堆的食物需要多少小时
int eatingHour(vector<int>&piles,int speed)
{
    if(speed <= 0) return -1;
    int hour = 0;
    for(auto &iter : piles)
    {
        hour += iter / speed;
        if(0 != iter % speed) hour += 1;
    }
    return hour;
}

题目要求吃完香蕉的最小速度,也就是速度要足够小,小到刚好在 H 小时内吃完所有的香蕉,所以是求速度的左侧边界 。

好了,分析完之后,写出代码:

int minEatingSpeed(vector<int> &piles, int h)
{
    //1小时最多能吃多少根香蕉
    int maxcount = 1;
    for (auto &iter : piles)
    {
        if (maxcount < iter) maxcount = iter;
    }
    //时间的校验
    if (h < 1 || h < (int)piles.size() )  return -1;
    int l_speed = 1;
    int r_speed = maxcount;
    while (l_speed <= r_speed)
    {
        int m = l_speed + (r_speed - l_speed) / 2;
        // eatingHour 函数代码见上文
        int hours = eatingHour(piles, m);
        if (hours == h)
        {
            // 求速度的左侧边界
            r_speed = m - 1;
        }
        else if (hours < h)
        {
            // hours 比 h 小,表示速度过大,边界需要往左边移动
            r_speed = m - 1;
        }
        else
        {
            // hours 比 h 大,表示速度国小,边界需要往右边移动
            l_speed = m + 1;
        }
    }
    return l_speed;
}

上述代码中,我们列出了 while 循环中的 if 的所有分支,是为了帮助理解的,大家可自行进行合并。

实例2:运送包裹

题目要求 船的运载能力, 船的运载能力和运输需要的天数成反比,运载能力越大,需要的天数越少,运载能力越小,需要的天数越多,也即存在 单调关系,下面定义出单调关系的函数。

//船的载重为 capcity 时,运载 weights 货物需要多少天
int shipDays(const vector<int> &weights, int capacity)
{
    //船载重校验
    if(capacity <= 0) return -1;
    int isize = (int)weights.size();
    int temp = 0;
    int days = 0;
    for(int i = 0; i < isize; ++i)
    {
        if(temp + weights[i] <= capacity)
        {
            temp += weights[i];
            continue;
        }
        ++days;
        temp = weights[i];
    }
    //还有剩余的,需要额外在运送一趟
    if(temp > 0)  ++days;
    return days;
}

题目中隐含的几个信息:

  • 船的最小载重需要大于等于传送带上最重包裹的重量,因为每次至少要装载一个包裹
  • 船的最大载重等于传送带上所有包裹的总重量,也即所有的包裹可以一次全部装上船
  • 船每天只能运送一趟包裹

确定了船的运载范围后,相当于确定了二分查找的区间,另外,题目求的是船的最小运载能力,相当于求运载能力的左侧边界。

分析到这里,就可以写出基本的查找框架了,这里直接给出代码了。

int shipWithinDays(vector<int> &weights, int days)
{
    int isize = (int)weights.size();
    if (isize <= 0) return 0;
    //最小载重,需要等于货物的最大重量
    int mincapacity = 0;
    //最大载重,全部货物重量的总和
    int maxcapacity = 0;
    for (auto &iter : weights)
    {
        maxcapacity += iter;
        if (iter > mincapacity)
        {
            mincapacity = iter;
        }
    }
    int l = mincapacity;
    int r = maxcapacity;
    while (l < r)
    {
        int m = l + (r - l) / 2;
        int d = shipDays(weights, m);
        if (d == days)
        {
            r = m - 1;
        }
        else if (d < days)
        {
            // d 比 days 小,表示船载重太大,载重边界需要往左移
            r = m - 1;
        }
        else
        {
            // d 比 days 大,表示船载重太小,载重边界需要往右移
            l = m + 1;
        }
    }
    return l;
}

小结总结来说,如果发现题目中存在单调关系,就可以尝试使用二分查找的思路来解决,分析单调关系,写出单调函数,搞清楚二分查找的范围,确定查找的代码框架,再进行边界细化,就能够写出最终代码。

以上就是详解C语言中二分查找的运用技巧的详细内容,更多关于C语言二分查找的资料请关注我们其它相关文章!

(0)

相关推荐

  • C语言快速排序与二分查找算法示例

    本文实例讲述了C语言二分排序与查找算法.分享给大家供大家参考,具体如下: 题目:首先产生随机数,再进行快速排序,再进行二分查找. 实现代码: #include <stdio.h> #include <stdlib.h> #include <time.h> void quiksort(int a[],int low,int high) { int i = low; int j = high; int temp = a[i]; if( low < high) { wh

  • 用C语言实现二分查找算法

    目录 一.前言 二.二分查找法 1.什么是二分查找法 2.如何用c语言来实现二分查找法 三.总结 总结 一.前言 假如今天我们需要在一个有序的数组中来寻找一个数的下标,就用"1,2,3,4,5,6,7,8,9"这九个数组成的数组来说,假如我们想寻找'2',那很简单我们只用从小到大开始寻找,寻找两次就完成了,但是我们想寻找'7',我们继续用从小到大挨个寻找,这就显得有点慢并且耗时长还没有效率,因此我们可以有一种全新的方法,二分查找法来解决这个问题. 二.二分查找法 1.什么是二分查找法

  • C语言编程中实现二分查找的简单入门实例

    架设有一个数组 v 已经按升序排列了,数组 v 有 n=20 个元素.数组中有个元素 x,如何知道 x 位于该数组的第几位呢? 解决这个问题的一个普遍方法就是二分查找法.下面是程序: #include <stdio.h> int binsearch(int x, int v[], int n); main() { int i, result, n; int wait; int x = 17; // 需要查找的数值 int v[19]; // 定义一个数组 // 给数组赋值 for(i = 0;

  • C语言二分查找算法及实现代码

    二分査找也称折半査找,其优点是查找速度快,缺点是要求所要査找的数据必须是有序序列.该算法的基本思想是将所要査找的序列的中间位置的数据与所要査找的元素进行比较,如果相等,则表示査找成功,否则将以该位置为基准将所要査找的序列分为左右两部分.接下来根据所要査找序列的升降序规律及中间元素与所查找元素的大小关系,来选择所要査找元素可能存在的那部分序列,对其采用同样的方法进行査找,直至能够确定所要查找的元素是否存在,具体的使用方法可通过下面的代码具体了解. #include <stdio.h> binar

  • C语言基础之二分查找知识最全汇总

    一.前言 在自学二分查找的过程中我想到了一些变化问题,有的自己就慢慢理解了,有的在网上找到了答案,奈何没有找到想要的总结归纳.我就斗胆自己写了一篇,号称史上最全.希望和我一样的伙伴可以少走一点弯路. 二分查找凭借其低时间复杂度O(log(n))成为了各个蒟蒻的入门知识,但是其衍生出的各种题目相较原题目而言就没有那么容易求解,以下借用c语言实现二分查找算法及其衍生.二分查找仅适用于事先已经排好序的顺序表.其基本思路就是每次取中间数,如果中间数大于所求数就向上查找,反之向下. 二.原始二分查找 1.

  • 一篇文章带你了解C语言二分查找

    目录 总结 我们常常需要对数据进行查找,修改,查找数据有许多方法,我们先看看最简单的顺序查找 int main() { int i, k = 0; scanf("%d", &k); int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int sz = sizeof(arr) / sizeof(arr[0]); for (i = 0; i < sz; i++) { if (arr[i] == k) { printf("

  • 一篇文章带你了解C语言二分查找的简单应用

    目录 前言 实战演练 思路分析 总结 前言 在有序数组中查找具体的某个数字n,可能有同学会说一个一个找,但是这样的效率实在太低,特别是对于有序的数组,效率太低.我们一般从中间元素开始找,查一次去掉一半数字,这种方法我们给它取名为折半查找即为二分查找,效率大大提高!怎么理解呢?如果有2的32次方个数字,我们最多只需查找32次,而一个一个数运气不好却是2的32次方次. 实战演练 这里我们先给出所写代码以及运行结果 在这里,给大家分析一下,首先,我们先创建一个有序数组arr[],然后我们把要查找的7用

  • 详解C语言中二分查找的运用技巧

    目录 基础的二分查 查找左侧边界 查找右侧边界 二分查找问题分析 实例1: 爱吃香蕉的珂珂 实例2:运送包裹 前篇文章聊到了二分查找的基础以及细节的处理问题,主要介绍了 查找和目标值相等的元素.查找第一个和目标值相等的元素.查找最后一个和目标值相等的元素 三种情况. 这些情况都适用于有序数组中查找指定元素 这个基本的场景,但实际应用中可能不会这么直接,甚至看了题目之后,都不会想到可以用二分查找算法来解决 . 本文就来分析下二分查找在实际中的应用,通过分析几个应用二分查找的实例,总结下能使用二分查

  • 详解Go语言中关于包导入必学的 8 个知识点

    1. 单行导入与多行导入 在 Go 语言中,一个包可包含多个 .go 文件(这些文件必须得在同一级文件夹中),只要这些 .go 文件的头部都使用 package 关键字声明了同一个包. 导入包主要可分为两种方式: 单行导入 import "fmt" import "sync" 多行导入 import( "fmt" "sync" ) 如你所见,Go 语言中 导入的包,必须得用双引号包含,在这里吐槽一下. 2. 使用别名 在一些场

  • 详解Go语言中泛型的实现原理与使用

    目录 前言 问题 解决方法 类型约束 重获类型安全 泛型使用场景 性能 虚拟方法表 单态化 Go 的实现 结论 前言 原文:A gentle introduction to generics in Go byDominik Braun 万俊峰Kevin:我看了觉得文章非常简单易懂,就征求了作者同意,翻译出来给大家分享一下. 本文是对泛型的基本思想及其在 Go 中的实现的一个比较容易理解的介绍,同时也是对围绕泛型的各种性能讨论的简单总结.首先,我们来看看泛型所解决的核心问题. 问题 假设我们想实现

  • 详解Go语言中配置文件使用与日志配置

    目录 项目结构调整 配置文件使用 日志配置 小结 接着上一篇的文章构建的项目:Go语学习笔记 - 环境安装.接口测试 只是简单的把GET和POST接口的使用测试了一下. 我还是想按照正常的项目结构调整一下,这篇笔记主要是三个部分:调整项目目录结构.增加配置文件使用.增加日志配置,很常规而且也是每个项目都需要用到的. 项目地址:github地址 项目结构调整 说先对项目目录结构调整一下,按照我自己的开发习惯,增加了几个目录. 项目结构如下图: 解释一下目录结构 app/constants:主要放置

  • 详解C语言中双向循环链表的实现

    目录 实现细节 辅助理解图 具体实现代码 1.对链表进行初始化 2.任意位置前的插入 3.任意位置的删除 4.头插和尾删 完整代码 头文件 具体函数 测试 实现细节 1.带一个哨兵位(哨兵节点,初始节点,不存储有效数据,用来方便后期数据的存储与查找) 2.与单向链表不同的是,双向链表中每个数据节点包含两个指针,分别指向前后两个节点 3.双向链表是循环的,其尾节点后不是空指针,而是与头部的哨兵节点通过指针相连 辅助理解图 具体实现代码 1.对链表进行初始化 初始化:哨兵位的前后指针均指向哨兵节点本

  • 详解Go语言中结构体与JSON间的转换

    目录 前言 结构体转 JSON JSON 解析结构体 小结 前言 在日常开发中,我们往往会将 JSON 解析成对应的结构体,反之也会将结构体转成 JSON.接下来本文会通过 JSON 包的两个函数,来介绍 JSON 与结构体之间的转换. 结构体转 JSON Marshal(v any) ([]byte, error):将 v 转成 JSON 数据,以 []byte 的形式返回. import ( "encoding/json" "fmt" ) type User s

  • 详解R语言中生存分析模型与时间依赖性ROC曲线可视化

    R语言简介 R是用于统计分析.绘图的语言和操作环境.R是属于GNU系统的一个自由.免费.源代码开放的软件,它是一个用于统计计算和统计制图的优秀工具. 人们通常使用接收者操作特征曲线(ROC)进行二元结果逻辑回归.但是,流行病学研究中感兴趣的结果通常是事件发生时间.使用随时间变化的时间依赖性ROC可以更全面地描述这种情况下的预测模型. 时间依赖性ROC定义 令 Mi为用于死亡率预测的基线(时间0)标量标记. 当随时间推移观察到结果时,其预测性能取决于评估时间 t.直观地说,在零时间测量的标记值应该

  • 详解R语言中的多项式回归、局部回归、核平滑和平滑样条回归模型

    在标准线性模型中,我们假设 .当线性假设无法满足时,可以考虑使用其他方法. 多项式回归 扩展可能是假设某些多项式函数, 同样,在标准线性模型方法(使用GLM的条件正态分布)中,参数  可以使用最小二乘法获得,其中  在  . 即使此多项式模型不是真正的多项式模型,也可能仍然是一个很好的近似值 .实际上,根据 Stone-Weierstrass定理,如果  在某个区间上是连续的,则有一个统一的近似值  ,通过多项式函数. 仅作说明,请考虑以下数据集 db = data.frame(x=xr,y=y

  • 详解R语言中的表达式、数学公式、特殊符号

      在R语言的绘图函数中,如果文本参数是合法的R语言表达式,那么这个表达式就被用Tex类似的规则进行文本格式化. y <- function(x) (exp(-(x^2)/2))/sqrt(2*pi) plot(y, -5, 5, main = expression(f(x) == frac(1,sqrt(2*pi))*e^(-frac(x^2,2))), lwd = 3, col = "blue") library(ggplot2) x <- seq(0, 2*pi, b

  • 详解C语言中不同类型的数据转换规则

    不同类型数据间的混合运算与类型转换 1.自动类型转换 在C语言中,自动类型转换遵循以下规则: ①若参与运算量的类型不同,则先转换成同一类型,然后进行运算 ②转换按数据长度增加的方向进行,以保证精度不降低.如int型和long型运算时,先把int量转成long型后再进行运算 a.若两种类型的字节数不同,转换成字节数高的类型 b.若两种类型的字节数相同,且一种有符号,一种无符号,则转换成无符号类型 ③所有的浮点运算都是以双精度进行的,即使是两个float单精度量运算的表达式,也要先转换成double

随机推荐