二分查找图
二叉树:
代码
#!/usr/bin/python #-*-coding:utf-8-*- #---------------------------------------------------------------------------------------- # to_do : binary find # authors: zuoxingyu # time : 2014-06-07 #---------------------------------------------------------------------------------------- loop=0 #二分次数 def binarySearch(lists,select): global loop loop=loop+1 is_none=False if lists!=[]: cen_num=len(lists)/2 #取命中值的INDEX tlag=lists[cen_num] #命中值 lt_list=lists[0:cen_num] #取命中值左边的小数列表 gt_list=lists[cen_num+1:]#取命中值右边的大数列表 print tlag,lt_list,gt_list if tlag==select: #命中,返回TRUE is_none=True return is_none elif select > tlag: #查找值大于M命中值,再在右边大数列表里找 return binarySearch(gt_list,select) elif select < tlag: #查找值小于命中值,再在左边小数列表里找 return binarySearch(lt_list,select) return is_none binarySearch([1,2,3,4,15,26,37,48,59],26) print ‘loop:‘,loop
执行效果:
[root@meizuDB MEIZUdb]# python binary_search.py 15 [1, 2, 3, 4] [26, 37, 48, 59] 48 [26, 37] [59] 37 [26] [] 26 [] [] loop: 4