欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

簡(jiǎn)介二分查找算法與相關(guān)的Python實(shí)現(xiàn)示例

 更新時(shí)間：2015年08月26日 12:12:26   作者：buaa_shang  
這篇文章主要介紹了二分查找算法與相關(guān)的Python實(shí)現(xiàn)示例,Binary Search同時(shí)也是算法學(xué)習(xí)當(dāng)中最基礎(chǔ)的知識(shí),需要的朋友可以參考下

二分查找Binary Search的思想：
以有序表表示靜態(tài)查找表時(shí)，查找函數(shù)可以用二分查找來(lái)實(shí)現(xiàn)。
二分查找（Binary Search）的查找過(guò)程是：先確定待查記錄所在的區(qū)間，然后逐步縮小區(qū)間直到找到或找不到該記錄為止。
1二分查找的時(shí)間復(fù)雜度是O(log(n))，最壞情況下的時(shí)間復(fù)雜度是O(n)。
假設(shè) low 指向區(qū)間下界，high 指向區(qū)間上界，mid 指向區(qū)間的中間位置，則 mid  = （low + high) / 2;
具體過(guò)程：
1.先將關(guān)鍵字與 mid 指向的元素比較，如果相等則返回mid。
2.關(guān)鍵字小于 mid 指向的元素關(guān)鍵字，則在 [ low,  mid-1 ]區(qū)間中繼續(xù)進(jìn)行二分查找。
3.關(guān)鍵字大于mid 指向的元素關(guān)鍵字，則在[ mid +1 , high] 區(qū)間中繼續(xù)進(jìn)行二分查找。

用Python實(shí)現(xiàn)二分查找示例：

>>> 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

相關(guān)文章

最新評(píng)論