二分查找算法（Python版）

[本文出自天外归云的博客园]

记性不好(@.@)，所以平时根本用不到的东西就算学过如果让我去想也会需要很多时间(*.*)！

二分查找算法

在一个有序数组中查找元素最快的算法，也就是折半查找法，先找一个数组中间位置（binary_index）的元素和目标元素（num）进行比较，如果binary_index位元素小于目标元素就在binary_index位右侧的子数组中继续递归查找，如果binary_index位元素大于目标元素就在binary_index位左侧的子数组中递归查找，如果binary_index位元素等于目标元素，那就是找到了目标元素。重点是确定每次查找的左边界或者右边界，这样才能通过加减binary_index位来确定最终的索引值。Python代码如下：

def binary_search(num,array,left_index=0):
    binary_index = len(array)/2
    if num < array[binary_index]:
        binary_search(num,array[0:binary_index],left_index)
    elif num > array[binary_index]:
        left_index = left_index + binary_index
        binary_search(num,array[binary_index:len(array)+1],left_index)
    else:
        print left_index+binary_index

if __name__ == '__main__':
    array = [-1,0,1,2,3,4,5,6,7,8,10,13,14,16,18,19,40]
    binary_search(0,array)

如果以后谁再问我二分查找，那时候我肯定又已经忘掉了，再想又要好久。记录一下吧，把关键处标红。T.T