??二分查找假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關鍵字大于查找關鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

• 優點：比較次數少，查找速度快，平均性能好；
• 缺點：要求待查表為有序順序表，且插入刪除困難。
• 二分查找方法適用于不經常變動而查找頻繁的有序列表。
• 二分查找最優時間復雜度是$O(1)$，最壞時間復雜度為$O(lo{g}_{2}n)$。
  假設總共有$n$個元素，查找操作次數為$k$，則每次查找的區間大小就是$n,\frac{n}{2},\frac{n}{4},\dots ,\frac{n}{2^k}$（接下來操作元素的剩余個數）。最好第一次操作就找到元素，時間復雜度為$O(n)$，最壞最后剩余的一個元素才是要查找的元素，即$\frac{n}{2^k}=1?k=lo{g}_{2}n$（假設是整數），時間復雜度為$O(lo{g}_{2}n)$

遞歸實現二分查找

# 返回 x 在 arr 中的索引，如果不存在返回 -1 def binarySearch (arr, l, r, x): # 基本判斷if l <= r: mid = (l+r)//2# 元素整好的中間位置if arr[mid] == x: return mid # 元素小于中間位置的元素，只需要再比較左邊的元素elif arr[mid] > x: return binarySearch(arr, l, mid-1, x) # 元素大于中間位置的元素，只需要再比較右邊的元素else: return binarySearch(arr, mid+1, r, x) else: # 不存在return -1# 函數調用 result = binarySearch(arr, 0, len(arr)-1, x)

非遞歸實現二分查找

def binarySearch (arr, x): n=len(arr)l,r=0,n-1while l<=r:mid=(l+r)//2if arr[mid]==x:return midelif arr[mid]>xr=mid-1else:l=mid+1return -1

總結

以上是生活随笔為你收集整理的二分查找时间复杂度及其Python实现的全部內容，希望文章能夠幫你解決所遇到的問題。

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