簡介二分查找算法與相關的Python實現示例

這篇文章主要介紹了二分查找算法與相關的Python實現示例,Binary Search同時也是算法學習當中最基礎的知識,需要的朋友可以參考下

二分查找Binary Search的思想：
以有序表表示靜態查找表時，查找函數可以用二分查找來實現。
二分查找（Binary Search）的查找過程是：先確定待查記錄所在的區間，然后逐步縮小區間直到找到或找不到該記錄為止。
1二分查找的時間復雜度是O(log(n))，最壞情況下的時間復雜度是O(n)。
假設 low 指向區間下界，high 指向區間上界，mid 指向區間的中間位置，則 mid  = （low + high) / 2;
具體過程：
1.先將關鍵字與 mid 指向的元素比較，如果相等則返回mid。
2.關鍵字小于 mid 指向的元素關鍵字，則在 [ low,  mid-1 ]區間中繼續進行二分查找。
3.關鍵字大于mid 指向的元素關鍵字，則在[ mid +1 , high] 區間中繼續進行二分查找。
用Python實現二分查找示例：    
>>> def find(self, num):
  l = len(self)
  first = 0
  end = l - 1
  mid = 0
  if l == 0:
   self.insert(0,num)
   return False
  while first < end:
   mid = (first + end)/2
   if num > self[mid]:
    first = mid + 1
   elif num < self[mid]:
    end = mid - 1
   else:
    break
  if first == end:
   if self[first] > num:
    self.insert(first, num)
    return False
   elif self[first] < num:
    self.insert(first + 1, num)
    return False
   else:
    return True
  elif first > end:
   self.insert(first, num)
   return False
  else:
   return True
 
>>> list_d = ['a','b','c','d','e','f','d','t']
>>> value_d = 't'
>>> aa=find(list_d,value_d)
>>> aa
True
>>> value_d='ha'
>>> aa=find(list_d,value_d)
>>> aa
False