二分查找

二分的思想在程序設計中有著廣泛的應用，例如，排序算法中的快速排序、歸并排序，數據結構中的二叉樹、堆、線段樹等。二分是一種常用且高效的算法，它的基本用途是在單調序列中進行查找和判定操作。

對于n個有序且沒有重復的元素（假設為升序），從中查找特定的某個元素x，我們可以將有序序列分成規模大致相等的兩部分，然后取中間元素與要查找的元素x進行比較，如果x等于中間元素，則查找成功，算法終止;如果x小于中間元素，則在序列的前半部分繼續查找，否則在序列的后半部分繼續查找。這樣就可以將查找的范圍縮小一半，然后在剩余的一半中繼續重復上面的方法進行查找。

這種每次都從中間元素開始比較，并且一次比較后就能把查找范圍縮小一半的方法，叫作二分查找。二分查找的時間復雜度是 O（logN），是一種效率較高的查找算法。

時間復雜度O（logN）

在常見的時間復雜度中，時間復雜度為O（logN）的算法十分高效，當數據規模增大n信時，耗時增大logN倍（這里的log以2為底）。例如，當數據增大256倍時，耗時增大8倍，因為2的8次方等于256。二分查找算法的時間復雜度為O（logN），每次查找排除掉一半的可能，1024個有序數據中最多查找10次就可以找到目標。

二分查找算法描述

用一維數組a存儲有序元素序列，用變量low和high分別表示查找范圍中第一個元素和最后一個元素的下標，mid表示查找范圍的中間位置對應元素的下標，x為要查找的元素。

（1）變量初始化，令low

總結

以上是生活随笔為你收集整理的二分查找和二分答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。