二分法查找介紹及實例詳解

二分法檢索介紹

二分法檢索（binary search）又稱折半檢索，二分法檢索的基本思想是設字典中的元素從小到大有序地存放在數組（array）中，

首先將給定值key與字典中間位置上元素的關鍵碼(key)比較，如果相等，則檢索成功；

#否則，若key小，則在字典前半部分中繼續進行二分法檢索;

若key大，則在字典後半部中繼續進行二分法檢索。

這樣，經過一次比較就縮小一半的檢索區間，如此進行下去，直到檢索成功或檢索失敗。

偶數個取中間2個其中任何一個作為中間元素

二分法檢索是一種效率較高的檢索方法，要求字典在順序表中按關鍵碼排序。

程式碼實例：

#!/usr/bin/env python
import sys 
def BinarySearch(haystack, needle):
  low = 0 
  high = len(haystack) - 1 
  while(low <= high):
    mid = (low + high)/2
    midval = haystack[mid]
    if midval < needle:
      low = mid + 1 
    elif midval > needle:
      high = mid - 1 
    else:
      print mid 
      return mid 
  print -1
  return -1
if __name__ == "__main__":
  haystack = [int(i) for i in list(sys.argv[1])]
  needle = int(sys.argv[2])
  BinarySearch(haystack ,needle)

執行:

python@pythontab:~$ python BinarySearch.py 123456789 4
3

備註:

1.'__'：由於python的類別成員都是公有、公開的被存取public，缺少像正統物件導向語言的私有private屬性。

於是就用__來將就一下，模擬私有屬性。這些__屬性往往是內部使用，通常不會改寫。也不用讀取。

加上2個底線的目的，一是不和普通公有屬性重名衝突，二是不讓物件的使用者(非開發者)隨意使用。

2.__name__ == "__main__"表示程式腳本是直接被執行的.

如果不等於表示腳本是被其他程式用import引入的.則其__name__屬性被設為模組名

以上是二分法查找介紹及實例詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！