二分查找
WIKI
In computer science, binary search, also known as half-interval search,[1] logarithmic search,[2] or binary chop,[3] is a search algorithm that finds the position of a target value within a sorted array.
简单查找VS二分查找
简单查找：从头开始查询
二分查找：二分查找就是将查找的键和子数组的中间键作比较，如果被查找的键小于中间键，就在左子数组继续查找；如果大于中间键，就在右子数组中查找，否则中间键就是要找的元素。
简单查找
二分查找
复杂度
O(n)
O(logn)
二分查找复杂度参考文献：
https://www.cnblogs.com/qiaozhoulin/p/5328090.html
Python代码
""" Input:list,item Output:index of item """ def binary_search(alist, aitem): low = 0 high = len(alist) - 1 while low <= high: mid = (low + high) / 2 guess = alist[mid] if guess == aitem: return mid if guess > aitem: high -= 1 else: low += 1 return None if __name__ == "__main__": alist = [1, 3, 5, 7, 8] aitem = 3 aindex = binary_search(alist, aitem)
