偉大的思想家莊子曾說過：「一尺之捶，日取其半，萬世不竭」。這在純數學理論上是成立的，我們可以在想象中将一尺無限分割為 1/2^n 尺。在實際生活中，我們卻不可能将其無限細分，現在已發現的最小粒子單元是誇克，也就是說我們将「一尺之捶」最多分到一誇克便不可再分。限制我們繼續細分的便是人類當前認知 有界。在算法世界，也有這樣一種算法，它将一種條件一分為二，二分為四，達到可分的邊界時停止。這就是二分算法。

來看一張動圖了解一下：

二分算法适用範圍很廣，隻要滿足以下兩個條件，就能使用二分算法。

• 單調
• 有界

單調的作用是讓我們可以找到一個判斷條件，每次分割後根據此判斷條件縮小搜索範圍；有界的作用是限制分割次數，在代碼中體現就是根據邊界終止循環。

我們在力扣題庫中點擊「二分查找」标簽，顯示如下：

粗略浏覽可以發現，二分查找的題目中很多都帶有「有序」、「排序」字樣，這是一個很明顯的單調條件，數組的長度是有限的，這是一個隐藏的有界條件。

二分法有固定的寫法：

kotlin 實現

​

例題：力扣 35. 搜索插入位置 力扣（點擊鍊接查看題目）

這是一道典型的二分題目。根據題目描述我們可以分析出：

• 因為數組是有序的，所以 target 越大，答案越大，答案和 target 單調遞增的關系
• 答案是有界的，在 [0, nums.size] 之間

根據二分法的固定寫法，我們可以很快寫出答案：

kotlin 實現

使用遞歸實現，需要将左邊界和右邊界作為參數傳給遞歸函數，代碼如下：

kotlin 實現

時間複雜度和空間複雜度分析

二分算法每次把搜索區域減少一半，所以時間複雜度是 O(log2n) 級的；

由于輔助變量是固定的，空間複雜度是 O(1).

一日，你到圖書館閱讀書籍後，帶了 n 本書出圖書館。這時，圖書館的報警器響起了「滴滴滴」的警報聲！

正在埋頭鑽研《算法導論》的圖書館阿姨聞聲走過來，說道：「呔！哪路小賊在此放肆，還不快将那本偷的書放下」。

于是你放下所有書，正準備一本本的試是哪一本書沒有辦理借閱手續，阿姨鄙夷的看你一眼，說道：「真笨，二分算法都不會。」

隻見阿姨先将一半的書通過報警器，報警器響起了滴滴聲。阿姨将這一半書再分一半，再次通過報警器，又響起了滴滴聲……在 log2n 次比較之後，阿姨很快找到了報警的那一本書。阿姨得意地對你炫耀說：「看，這樣多高效！」

然後，你在阿姨的帶領下辦理了那一本書的借閱手續，利用阿姨會二分算法，成功帶走了剩餘 n-1 本也沒有辦理借閱手續的書！

本文作者：Alpinist Wang

聲明：本文歸 “力扣” 版權所有，如需轉載請聯系。

文中部分圖片來源于網絡，為非商業用途使用，如有侵權聯系删除。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!