2018-01-31二分查找 2018-01-31二分查找

04-22
迭代简化版思路:
参考老版py 2.4之前bisect_right

def bisect_right(a, x, lo=0, hi=None): if hi is None: hi = len(a) while lo < hi: mid = (lo + hi)//2 if x < a[mid] : hi = mid else: lo = mid + 1 return lo

04-15
递归版：

思路：在一个升序的列表中，比mid大找右边，比mid小赵左边。
注意：条件判断后调用自身时用return： return func(n),如果直接调用递归会出现很多次return.

def Find_row(target,row): n = len(row) - 1 _min = 0 _max = n mid = n/2 # print 'mid _max',mid,_max # TODO if n == 0: # print target,row[0] if target == row[0]: # print 'Equal==' return True else: # print '??' return False if n > 0: if target == row[mid]: # print 'Equal' return True elif target < row[mid]: # print 'lower' if mid == _min: return False else: return Find_row(target, row[:mid]) else: # if target > row[mid]: # print 'bigger' return Find_row(target, row[mid+1:])

test

t = [i for i in range(10)] row = [1,2,3,4,5,6,7,8,9,10] for _x in t: if Find_row(_x,row): print _x,'Y' else: print _x,'N'

输出

0 N 1 Y 2 Y 3 Y 4 Y 5 Y 6 Y 7 Y 8 Y 9 Y

—————————————————————————————
迭代循环版 【2018-01-31二分查找】放上之前写的二分查找,复杂度（nlogn）

def b_Search(x,item): first = 0 last = len(x)-1 found = False while first<=last and not found: mid = (first+last)//2 # print mid,last,first if item == x[mid]: found == True breakelse: if first==last and item != x[mid]: found = True # print '缺失值' mid = -1 else: if x[mid] > item: first = mid+1 else: last = mid-1return mid