二分查找Binary Search的思想：
以有序表表示靜態(tài)查找表時(shí)，查找函數(shù)可以用二分查找來實(shí)現(xiàn)。
二分查找（Binary Search）的查找過程是：先確定待查記錄所在的區(qū)間，然后逐步縮小區(qū)間直到找到或找不到該記錄為止。
1二分查找的時(shí)間復(fù)雜度是O(log(n))，最壞情況下的時(shí)間復(fù)雜度是O(n)。
假設(shè) low 指向區(qū)間下界，high 指向區(qū)間上界，mid 指向區(qū)間的中間位置，則 mid = （low + high) / 2;
具體過程：
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)>>> aaTrue>>> value_d='ha'>>> aa=find(list_d,value_d)>>> aaFalse
新聞熱點(diǎn)
疑難解答
圖片精選
