二分查找：每次砍掉一半，把“大海捞针“变成“几步到位“

引子老王的翻字典绝活还记得那位一路从查找江湖杀进图的世界、又刚刚拜入分治法门下、领悟了化整为零心法的老王吗这天老王的小孙子捧着一本厚厚的《新华字典》跑来求助“爷爷爷爷老师让我查’懵’这个字可这字典有一千多页、几万个字啊我从第一页开始一页一页翻翻了半天还没找到手都翻酸了这得翻到啥时候啊”老王接过字典胸有成竹地笑了“傻孙子谁教你从头一页一页翻的看爷爷的”只见老王啪地一下翻到字典正中间瞄了一眼——这页是M开头的字。懵’是 m 打头正好在这附近他又往后翻了几页“哗哗哗”没几下就精准地戳中了那个懵字全程不超过十下小孙子看得目瞪口呆。老王却若有所悟摸着胡子嘀咕咦?我这翻字典的’土办法’,怎么越想越眼熟?——先翻中间,看看要找的字在前半本还是后半本,然后就把另外半本’扔掉’不管了,在剩下的半本里再翻中间……这不就是前几天刚学的’分治’里那个’每次砍掉一半’的劲儿吗?几万个字,我没几下就揪出来了!这’砍一半’的查找绝活,到底是个啥讲究?讲不讲条件?快得有没有个准数?老王这一摸胡子正摸中了查找江湖里最经典、最优雅、也最锋利的一把快刀——二分查找Binary Search。它的思想全藏在老王翻字典的绝活里与其从头到尾一个一个找顺序查找慢如蜗牛不如每次都看正中间那个跟要找的目标比一比立刻就能砍掉一半没希望的范围在剩下的一半里**再砍一半……**几下就能精准命中老王搓搓手“翻中间、扔一半、再翻中间……原来我这翻字典的土办法,是把’快刀’啊!可它凭啥能’砍一半’?随便一堆东西都能这么砍吗?快说说门道!”第一章一个铁打的前提——必须先排好队老王刚要得意我们就得先给他泼盆冷静水——二分查找这把快刀虽利却有一个雷打不动、绝不能破的前提铁打的前提要查找的这堆数据必须是事先排好序的从小到大或从大到小为什么老王翻字典翻得快根子就在字典是按拼音/笔画排好序的正因为排好了序他翻到中间看到M才能笃定地判断“我要找的 m 在 M 附近前面 A~L 那半本看都不用看直接扔掉”┌────────────────────────────────────────────────┐ │ 为啥必须先排好队? │ │ │ │ 排好序的(字典): │ │ 翻到中间看到M → 笃定懵在后半 → 扔掉前半! │ │ 每一刀都砍得理直气壮! ⚡ │ │ │ │ 没排序的(一麻袋乱字条): │ │ 抽中间一张是猫 → 那懵在哪半? │ │ →鬼知道!乱的!砍哪半都可能砍错! │ │ → 只能一张张翻(顺序查找),二分使不上劲! │ └────────────────────────────────────────────────┘关键真相“排好序”就是二分查找的通行证正因为有序中间那个才成了一座完美的路标——看它一眼就知道目标在左半还是右半从而能放心地砍掉另一半。没有序就没有路标二分这把快刀就彻底失了用武之地老王恍然“原来如此!得先排好队,中间那个’才靠谱、才敢扔一半!乱糟糟的一堆,砍哪半都是瞎砍!这前提,可太关键了!”好前提讲清了我们看看这把快刀具体怎么挥。第二章核心招法——“掐头、去尾、盯中间”二分查找挥刀就靠两个指针 一个中间。我们设定一个左指针low盯着当前查找范围的最左边一个右指针high盯着当前查找范围的最右边每次都看中间mid左右指针正中间那个。招法就三句口诀反复挥二分三句诀反复做看中间取出 low 和 high 正中间那个数mid比一比中间这个 目标 →找到了收刀中间这个 目标 → 目标在右半→左指针跳到中间右边砍掉左半中间这个 目标 → 目标在左半→右指针跳到中间左边砍掉右半缩范围在砍剩的半边里回到第1步继续看中间……直到找到或范围缩没了说明没有这个数。老王眼睛一亮“掐着头尾两个指针,死死盯住中间那个——比一下,就扔掉没希望的半边,把指针往中间一收!越收越窄,几下就逼出来了!走一遍给我看看!”好我们就来挥几刀。第三章手把手挥几刀——在11个数里揪出23假设有这样一排已经排好序的数我们要找23下标: 0 1 2 3 4 5 6 7 8 9 10 数值: [ 3 8 12 17 23 31 44 56 68 72 91] ↑low high↑ 第1刀看中间low0, high10 → 中间 mid(010)/25 → 数值是 31 比一比:31 23(要找的) → 目标在【左半】! → 砍掉右半!右指针跳到中间左边:high 5-1 4 剩下的范围:[3 8 12 17 23] (下标0~4) 第2刀在剩下的左半里再看中间low0, high4 → 中间 mid(04)/22 → 数值是 12 比一比:12 23 → 目标在【右半】! → 砍掉左半!左指针跳到中间右边:low 21 3 剩下的范围:[17 23] (下标3~4) 第3刀再看中间low3, high4 → 中间 mid(34)/23 → 数值是 17 比一比:17 23 → 目标在【右半】! → 砍掉左半!左指针:low 31 4 剩下的范围:[23] (就剩下标4这一个了!) 第4刀再看中间low4, high4 → 中间 mid4 → 数值是 23 比一比:23 23 → 找到了!就在下标4!收刀!┌────────────────────────────────────────────────┐ │ 仅仅4刀,就在11个数里揪出了23! │ │ │ │ 31(砍掉右半5个) → 12(砍掉左半2个) │ │ → 17(砍掉左半1个) → 23(命中!) │ │ │ │ 对比从头一个个找:可能要找5次才到23, │ │ 而二分,每一刀都砍掉一大片,稳稳4刀搞定! │ └────────────────────────────────────────────────┘老王看得拍案叫绝“妙极了!它根本不挨个看!每一刀,都拿中间那个当’路标’,唰’地砍掉没希望的一大半!范围像被快刀削过一样,飞速变窄,几刀就把目标逼到墙角!这刀法,太干脆利落了!”第四章威力揭秘——快到什么程度老王最关心这’砍一半’到底能快多少我们就算笔账看看这把快刀的恐怖威力。┌────────────────────────────────────────────────┐ │ 在【100万】个排好序的数里找一个数: │ │ │ │ 【顺序查找】一个个看: │ │ 运气差,要看100万次! │ │ │ │ 【二分查找】每次砍一半: │ │ 100万 → 50万 → 25万 → ... → 1 │ │ 砍多少刀见底? 大约只要【20刀】! ⚡ │ │ │ │ → 100万次 vs 20次,快了五万倍! │ └────────────────────────────────────────────────┘威力的根源二分查找每挥一刀范围就对半砍。100万砍一半是50万再砍是25万……砍二十下就从100万逼到了1这种指数级缩小让它的速度快到令人发指——专业上叫O(log N)对数级是查找算法里梦寐以求的速度。更震撼的是哪怕数据涨到10亿二分也不过多挥十刀而已约30刀搞定数据翻天覆地地涨它的工作量却只是不痛不痒地多砍几刀——这就是对数级的恐怖之处老王倒吸一口凉气“100万个数,20刀就揪出来?!10亿个也才30刀?!这数据涨上天,它就多砍几刀的事儿……这哪是查找,这简直是’神仙快刀’啊!”第五章快刀的两面——它也有讲究老王佩服得五体投地我们得诚实地补上它的另一面让他用得明白。┌────────────────────────────────────────────────┐ │ 二分查找这把快刀,有得也有舍: │ │ │ │ ✅ 得:查找快如闪电(O(log N)),数据越多越显神威! │ │ │ │ ⚠️ 舍①:必须先排好序——而排序本身要花时间! │ │ → 若只查一两次,排序的功夫还不如直接挨个找; │ │ 但若要【反复查千万次】,排一次序一劳永逸,超值!│ │ │ │ ⚠️ 舍②:数据最好能按下标直接跳取(像数组)。 │ │ 若是得顺着一个个走的链表,跳到中间都费劲, │ │ 二分的优势就大打折扣了! │ └────────────────────────────────────────────────┘用刀的智慧二分查找是一次排序、终身受益的买卖——它最适合那种排好一次序、之后要反复查找无数次的场景比如查字典、数据库索引。排序的成本一次性付清后面每一次查找都快如闪电、稳赚不赔但若数据老在变、查得又少或者结构上够不着中间这把快刀就未必趁手了。老王点头“懂了!天下没有白占的便宜。它快是真快,但得先排好队(花一次排序的功夫),还得是’够得着中间’的数据。最划算的,是排一次、查千万次——那这把快刀,就是稳赚不赔的神兵!”第六章终极总结——二分查找到底妙在哪老王把二分查找的智慧浓缩成一张表贴在了查找江湖那一页上┌────────────────┬──────────────────────────────────┐ │ 二分查找 │ 说明 │ ├────────────────┼──────────────────────────────────┤ │ 核心思想 │ 看中间、比一比、砍掉没希望的一半 │ │ 铁打的前提 │ 数据必须先排好序! │ │ 招法 │ 左右指针掐住,反复看中间、缩范围 │ │ 快到什么程度 │ O(log N):100万个数,20刀搞定!⚡ │ │ 越多越神 │ 数据翻天涨,也只多砍几刀 │ │ 它的舍 │ 要先排序;最好能直接跳取(数组) │ │ 最佳战场 │ 排一次序、反复查千万次(字典/索引) │ │ 一句话 │ 每次砍一半,把大海捞针变几步到位! │ └────────────────┴──────────────────────────────────┘老王摸着这张表悟出了二分查找的题眼我总算把这翻字典的快刀看透了——它的高明,不在’力大’,而在’巧砍’:每一刀,都不贪心地去看全部,只盯住那’正中间’的一个,跟目标比一比,就敢把没希望的整整一半**,干脆利落地砍掉!**就靠这’看一眼、砍一半’的笃定,它把’几万里挑一’的大海捞针,削成了’几步到位’的轻巧活儿!不过它有个雷打不动的根:东西必须先排好队——有了’序’这个路标,它才敢一刀刀放心地砍。原来,真正的快,不是埋头蛮找,而是看准了路标,每一步都果断舍掉一半的’不可能’!尾声一把每次砍掉一半的快刀亦是人生的智慧老王这场对二分查找的钻研从翻字典的土办法出发看清了必须先排好序的铁打前提更领略了看中间、砍一半那令人发指的神速——终于把查找江湖里这把最锋利的快刀握进了手心。但当我们合上书会发现这把每次砍掉一半的快刀背后竟也舒展着几分耐人寻味的人生哲理。第一高效的关键常常不是找到对的而是果断排除一半错的。二分查找最锋利之处恰恰不在于它每一刀都找到了目标而在于它每一刀都果断地、毫不留恋地砍掉那没希望的一半——正是这一次次排除让它飞速逼近了答案。这何尝不是一种深刻的处世智慧我们做选择、找方向时总执着于一下子找到那个完美的对的答案结果在无穷的可能里反复纠结、迟迟定不下来。可高手的做法往往相反——他们未必一眼就知道’什么是对的’,却很擅长果断地判断’什么是明显错的、不可能的’,然后毫不犹豫地把那一大半排除掉!范围一次次缩小答案自然水落石出。与其苦苦寻觅那个’唯一的正确’,不如先果断舍弃那些’明显的错误’——排除法,often是逼近真相最快的路。第二“看准路标比埋头狂奔重要——而路标来自事先的理顺”。二分快刀之所以快前提是数据排好了序——是那个序给了它判断方向的路标。没有路标再快的刀也只能瞎砍。这给我们一个朴素的提醒真正的高效从不是一头扎进去埋头狂奔而是先有一个’理顺了的秩序、看得清的路标’。那些做事极有效率的人往往不是手脚最快的而是最舍得在动手前先把信息理顺、把头绪排清、把’路标’立好的人。磨刀不误砍柴工——事先花力气’排好序、立路标’,看似慢了一步,却让之后的每一步,都走得又快又准、绝不白费。凡事预则立先理顺再出发。第三肯付一次排序的成本方能享千万次查找的红利。二分查找最划算的买卖是排一次序查千万次——它肯在前期付出排序那一次性的辛苦从而换来此后每一次查找都快如闪电的长久红利。这是一种了不起的长远眼光。生活里多少人只图眼前省事不肯付那一次性整理的成本——文件从不归类、知识从不沉淀、技能从不打底结果每次用时都得手忙脚乱地从头乱翻一辈子在重复的低效里打转。而聪明人懂得:某些’一次性的投入’(把东西归好类、把基础打扎实、把系统建起来),虽然当下要费些功夫,却能让未来千万次的’查找’都一劳永逸、稳赚不赔。别为了省一次的力而搭上无数次的累——肯下’排序’的笨功夫,才配享’秒查’的真红利。下次当你啪地翻开字典、几下就戳中那个字当搜索引擎在亿万网页里瞬间为你捧出答案时请记得——在那看不见的深处有一把二分查找的快刀它从不埋头蛮找只在那理顺了的秩序里看准中间的路标每一刀都果断地砍掉一半的’不可能’于是再浩瀚如海的茫茫数据也被它三两下、轻巧巧地逼成了你眼前那个唯一的答案。“二分查找”就是这门关于果断排除错的、先理顺立路标、肯付一次成本享长久红利的、朴素而深刻的智慧。它告诉我们高效的关键常常不是找到对的而是果断排除一半错的看准路标比埋头狂奔重要而路标来自事先的理顺肯付一次排序的成本方能享千万次查找的红利。它像一句朴素的箴言提醒着我们——别执着于一眼找到那个唯一的对先果断舍掉那些明显的错答案自会水落石出别一头扎进去埋头狂奔先把头绪理顺、把路标立好之后每一步才又快又准肯付那一次性理顺的笨功夫才配享此后次次秒达的真红利——一个懂得善用排除、先理后行、长远投入的人才能像那把每次砍掉一半的快刀纵使面对浩瀚如海、几万里挑一的茫茫也总能看准路标果断地砍去一半的不可能三两下便从万千之中稳稳逼出那个唯一的答案。这就是藏在二分查找背后那把每次砍掉一半的快刀最深、也最美的浪漫。