经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C 语言 » 查看文章
详解C语言中二分查找的运用技巧
来源:jb51  时间:2022/3/29 13:47:34  对本文有异议

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

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

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

基础的二分查

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

查找左侧边界

  1. int binary_search_firstequal(vector<int> &vec, int target)
  2. {
  3. int ilen = (int)vec.size();
  4. if(ilen <= 0) return -1;
  5. int left = 0;
  6. int right = ilen - 1;
  7. while (left <= right)
  8. {
  9. int mid = left + (right - left) / 2;
  10. //找到了目标,继续向左查找目标
  11. if (target == vec[mid]) right = mid - 1;
  12. else if(target < vec[mid]) right = mid -1;
  13. else left = mid + 1;
  14. }
  15. if(right + 1 < ilen && vec[right + 1] == target) return right+1;
  16. return -1;
  17. }

查找右侧边界

  1. int binary_search_lastequal(vector<int> &vec, int target)
  2. {
  3. int ilen = (int)vec.size();
  4. if(ilen <= 0) return -1;
  5. int left = 0;
  6. int right = ilen - 1;
  7. while (left <= right)
  8. {
  9. int mid = left + (right - left) / 2;
  10. //找到了目标,继续向右查找目标
  11. if (target == vec[mid]) left = mid + 1;
  12. else if(target < vec[mid]) right = mid -1;
  13. else left = mid + 1;
  14. }
  15. if(left - 1 < ilen && vec[left - 1] == target) return left - 1;
  16. return -1;
  17. }

二分查找问题分析

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

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

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

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

  1. int func(vector<int>&vec,int index)
  2. {
  3. return vec[index];
  4. }
  5. int search(vector<int>&vec,int target)
  6. {
  7. while (left <= right)
  8. {
  9. int mid = left + (right - left) / 2;
  10. if (target == func(vec,mid))
  11. {
  12. ....
  13. }
  14. else if(target > func(vec,mid))
  15. {
  16. ...
  17. }
  18. else
  19. {
  20. ...
  21. }
  22. }
  23. }

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

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

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

实例1: 爱吃香蕉的珂珂

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

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

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

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

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

  1. int maxspeed = 1;
  2. for(auto &elem : vec)
  3. {
  4. if(elem > maxspeed) maxspeed = elem;
  5. }+

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

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

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

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

  1. // 速度为 speed 时,吃完所有堆的食物需要多少小时
  2. int eatingHour(vector<int>&piles,int speed)
  3. {
  4. if(speed <= 0) return -1;
  5. int hour = 0;
  6. for(auto &iter : piles)
  7. {
  8. hour += iter / speed;
  9. if(0 != iter % speed) hour += 1;
  10. }
  11. return hour;
  12. }

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

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

  1. int minEatingSpeed(vector<int> &piles, int h)
  2. {
  3. //1小时最多能吃多少根香蕉
  4. int maxcount = 1;
  5. for (auto &iter : piles)
  6. {
  7. if (maxcount < iter) maxcount = iter;
  8. }
  9. //时间的校验
  10. if (h < 1 || h < (int)piles.size() ) return -1;
  11. int l_speed = 1;
  12. int r_speed = maxcount;
  13. while (l_speed <= r_speed)
  14. {
  15. int m = l_speed + (r_speed - l_speed) / 2;
  16. // eatingHour 函数代码见上文
  17. int hours = eatingHour(piles, m);
  18. if (hours == h)
  19. {
  20. // 求速度的左侧边界
  21. r_speed = m - 1;
  22. }
  23. else if (hours < h)
  24. {
  25. // hours 比 h 小,表示速度过大,边界需要往左边移动
  26. r_speed = m - 1;
  27. }
  28. else
  29. {
  30. // hours 比 h 大,表示速度国小,边界需要往右边移动
  31. l_speed = m + 1;
  32. }
  33. }
  34. return l_speed;
  35. }

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

实例2:运送包裹

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

  1. //船的载重为 capcity 时,运载 weights 货物需要多少天
  2. int shipDays(const vector<int> &weights, int capacity)
  3. {
  4. //船载重校验
  5. if(capacity <= 0) return -1;
  6. int isize = (int)weights.size();
  7. int temp = 0;
  8. int days = 0;
  9. for(int i = 0; i < isize; ++i)
  10. {
  11. if(temp + weights[i] <= capacity)
  12. {
  13. temp += weights[i];
  14. continue;
  15. }
  16. ++days;
  17. temp = weights[i];
  18. }
  19. //还有剩余的,需要额外在运送一趟
  20. if(temp > 0) ++days;
  21. return days;
  22. }

题目中隐含的几个信息:

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

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

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

  1. int shipWithinDays(vector<int> &weights, int days)
  2. {
  3. int isize = (int)weights.size();
  4. if (isize <= 0) return 0;
  5. //最小载重,需要等于货物的最大重量
  6. int mincapacity = 0;
  7. //最大载重,全部货物重量的总和
  8. int maxcapacity = 0;
  9. for (auto &iter : weights)
  10. {
  11. maxcapacity += iter;
  12. if (iter > mincapacity)
  13. {
  14. mincapacity = iter;
  15. }
  16. }
  17. int l = mincapacity;
  18. int r = maxcapacity;
  19. while (l < r)
  20. {
  21. int m = l + (r - l) / 2;
  22. int d = shipDays(weights, m);
  23. if (d == days)
  24. {
  25. r = m - 1;
  26. }
  27. else if (d < days)
  28. {
  29. // d 比 days 小,表示船载重太大,载重边界需要往左移
  30. r = m - 1;
  31. }
  32. else
  33. {
  34. // d 比 days 大,表示船载重太小,载重边界需要往右移
  35. l = m + 1;
  36. }
  37. }
  38. return l;
  39. }

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

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

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号