快捷導航

Python二分法搜索算法實例分析

更新時間：2015年05月11日 16:06:55 作者：像風一樣的自由

這篇文章主要介紹了Python二分法搜索算法,實例分析了Python實現(xiàn)二分法的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下

本文實例分析了Python二分法搜索算法。分享給大家供大家參考。具體分析如下：

今天看書時，書上提到二分法雖然道理簡單，大家一聽就明白但是真正能一次性寫出別出錯的實現(xiàn)還是比較難的，即使給了你充足的時間，比如1小時。如果你不是特別認真的話，可能還是會出一些這樣那樣的錯誤，所以就嘗試了自己去實現(xiàn)一下，看能否一次通過，結(jié)果自然不言而喻，雖然用的時間不長，但是我失敗了，呵呵。

個人覺得失敗的最主要原因是自己沒有認真的先想好這個思路和可能出現(xiàn)的分支情況，而是直接憑主觀臆想就去寫代碼了，完全正中書上所說的行為，所以也如書上所說，出錯了。后經(jīng)調(diào)試應(yīng)該是得到了基本的正確算法，內(nèi)容如下：

#!/usr/bin/env python
#encoding: utf-8
def half_search(search_arr, search_str):
  lb = 0
  ub = len(search_arr) - 1
  for i in range(ub/2 + 1):
    if lb > ub:
      return -1
    mid = (ub + lb)/2
    if search_arr[mid] == search_str:
      return mid
    elif search_arr[mid] > search_str:
      ub = mid - 1
    else:
      lb = mid + 1
if __name__=='__main__':
  arr = [10,20,30,40,50,60,70]
  print half_search(arr, 1)
  print half_search(arr, 11)
  print half_search(arr, 22)
  print half_search(arr, 33)
  print half_search(arr, 40)
  print half_search(arr, 55)
  print half_search(arr, 66)
  print half_search(arr, 70)
  print half_search(arr, 8)

結(jié)果：

-1 
-1 
-1 
-1 
3 
-1 
-1 
6 
-1

正整數(shù)代表在數(shù)組中的下標，3那就是第4個位置；-1代表不存在

總結(jié)：

實現(xiàn)簡單的算法之前，如果已經(jīng)有了一套最簡易的實現(xiàn)【比如直接打印100條相似的內(nèi)容】，不妨要想想是否還有更精巧的實現(xiàn)【可否用循環(huán)+參數(shù)化替代】；實現(xiàn)稍微復雜點的算法時，不妨先在紙上畫出各種可能的驗證情況，避免實現(xiàn)是缺胳膊短腿的；還有一點就是算法什么的還是要多練，不然稍微復雜的過一陣可能就會忘記細節(jié)了。我想這就叫術(shù)業(yè)有專攻吧！

希望本文所述對大家的Python程序設(shè)計有所幫助。

您可能感興趣的文章: