二分查找

二分查找是著名、高效并有应用广泛的查找算法。

二分常规实现

1.循环实现

下面我用python语言实现循环和递归二分查找有序线性表

2.递归实现

算法总结

二分查找要求遍历的线性表采用顺序存储结构，实现原理是算法使用两个变量low和high，并保证如果键在数组中则它一定在array[low...high]中，然后方法进入一个循环，不断将数组的中间键（索引为mid）和被查找的键比较。如果被查找的键等于array[mid],返回mid。否则算法就缩小一半范围，如果被查找的键小于array[mid],就继续在左半边查找，如果大于就在右半边查找。算法找到被查找的键或是查找范围为空时该过程结束。二分查找之所以快是因为它只需要检查很小的条目（相对于数组的长度）就能够找到目标元素（或者确认元素不存在）。在有序数组中进行二分查找的时间复杂度为：O(log2n)