二分查找算法

二分查找算法是一个即简单与好用的算法。时间复杂度和空间复杂度都很不错。下面是简单的实现

＃coding:utf-8
＃值得注意的是输入的数组必须是有序的!
def binarySearch(num,target):    
  low = 0    
  high = len(num) - 1     
  while high >= low:        
    mid = (low + high) // 2 #将原数组二分        
    midValue = num[mid]        
    if midValue < target: #target比中值大表明要找的在右边            
      low = mid + 1        
    elif midValue > target:            
      high = mid - 1        
    else:            
      return (mid,midValue) #返回查找的值和索引
if __name__ == '__main__':    
  num = [0, 1, 3, 5, 6, 7, 8, 9]    
  print binarySearch(num, 6)