LeetCode面试刷题技巧-二分查找算法代码思路解析

举报
格图洛书 发表于 2021/11/19 00:44:06 2021/11/19
【摘要】 二分查找的思想 提及二分查找算法,我想大部分人都不陌生,就算不是学计算机的,基本上也都使用过二分查找的思想,不信的话,且听我慢慢为你道来。 不知道你有没有玩过这样一个游戏,猜数字。就是说一个人心里想了一个数字,这个数字有范围,然后另外一个人去猜,每次猜的时候,另一个人会告诉你是猜的大了,还是小了,亦或是猜中了,看怎么样才能够最快的猜...

二分查找的思想

提及二分查找算法,我想大部分人都不陌生,就算不是学计算机的,基本上也都使用过二分查找的思想,不信的话,且听我慢慢为你道来。

不知道你有没有玩过这样一个游戏,猜数字。就是说一个人心里想了一个数字,这个数字有范围,然后另外一个人去猜,每次猜的时候,另一个人会告诉你是猜的大了,还是小了,亦或是猜中了,看怎么样才能够最快的猜中另一个人想的数字。

想必大部分人都玩过吧,比如说,数字范围是 0 - 100,那我想你肯定是先猜 50,如果说猜大了,那就去猜 25,否则去猜 75, 以此类推,直到被猜的区间长度变为 1 或者你提前猜中了。

总结来说,就是每次二分的过程中,将待查找的区间长度变为原来的一半,直到找到要查找的值或者区间当中不存在待查找的值。

计算机中的二分查找算法

对应到计算机当中的二分查找算法又是啥样的呢?那就是给定一个数组,然后查找值等于给定值的元素。说到这,你是不是觉得二分查找很简单,没必要单独花一篇文章进行讲解?

我不能说你理解的不对,确实,简单的二分查找算法挺简单的,但是你如果以为这就是全部的二分查找算法的话,那你就错了。

二分查找算法有很多变体问题,这些问题在生活当中还非常常用,而且写起来非常烧脑。

唐纳德.克努特 (Donald E.Knuth)在《计算机程序设计艺术》的第 3 卷《排序和查找》中提到:

尽管第一个二分查找算法于 1946 年出现,然而第一个完全正确的二分查找算法实现直到 1962 年才出

文章来源: wenyusuran.blog.csdn.net,作者:文宇肃然,版权归原作者所有,如需转载,请联系作者。

原文链接:wenyusuran.blog.csdn.net/article/details/118087400

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。