python实现二分法详解

学习python的同学，特别是新人可能会对各种算法搞的比较迷糊，在我自己学习二分法的时候，思路是很清晰的，我就想先百度一下，看看大神是怎么写的，验证一下自己的代码吧，结果发现照着写下来也根本没办法看。这里还是要顺带吐槽一下万恶的百度。搜索的结果简直了。

好了，言归正题，先简单讲一下二分法吧。 下面的是百度的解释：

对于区间[a，b]上连续不断且f（a）·f（b）<0的函数y=f（x），通过不断地把函数f（x）的零点所在的区##间一分为二，使区间的两个端点逐步逼近零点，进而得到零点近似值的方法叫二分法。

说的算是比较透彻，懂的都懂了，没懂的啥也没懂。我来说一下我的理解吧。不对的也欢迎指出，共勉。

1、二分法的前提必须是在一个有序的数列中进行查找（重要） 何为“有序”？ 就是列表的顺序必须是排列好的，而不能是乱序的。可以看看下面的例子 有序的样式应该是这样的 array = [1,2,3,4,5,6,7,8,9] 无序的就是乱的 array = [1,98,76,34,12] 2、所谓的“二分法”是通过获取列表的中间位置后，根据中间位置来进行判断需要查找的数字的大小在左边还是右边 继续举个栗子 array = [1,2,3,4,5,6,7,8,9] 如果我们想找到上面这个列表中的数字5的办法实际最简单的就是遍历这个列表

for i in array:
if i == 5:
print (array.index(i))
 >>> 4

    上面就是最简单的遍历查询方法了，但是如果列表的长度非常长的时候，或者在我们要查找的列表最后面的话，遍历查询法就比较慢了。

实际命题 #我们可以从列表中间先取出最中间位置的数，然后判断他是否大于我们需要寻找的数。 # array = [1,2,3,4,5,6,7,8,9] 如果我们要从里面找到“8”，那么按照遍历的方法需要在循环第7次的时候才可以找到。

接下来我们用二分法的思路来处理上面这个问题 #1、首先先获取array的列表长度 2、取得中间的数字，这个列表长度是8(从0开始计算)，中间的数字位数就是4 3、那么先拿array的第四位数字“5”和我们要找的数字“8”对比，发现是比8小的 4、那么我们让循环变成第五位在开始判断是否是我们要找的数字 5、...一直到找到为止 通过二分法，上面这个例子，实际只要循环4次就可以找到我们想要的数字。对比遍历查找的方式，就减少了3次运算，提升了效率。

那么接下来，我们已经理解了实现的原理，现在来开始写这个脚本就非常简单了。直接上代码。注释都写在里面了。

     #codeing:gb18030
    def ErFenFa(array,key):
          print ('列表长度为:',len(array)) #先计算列表的长度
          mid = int((len(array)-1)/2)
          print ('列表中间位数为:',mid)
          min = 0
          max = len(array)-1
          print ('即将开始判断，初始化最小数为0，最大数为:%s'%max)
          print ('-'*10)
          count = 0
          while True:
              center = int((min + max) / 2)
              print ('本次查找的位置:',center)
              if array[center] > key:
                #这种说明查找到的数字大于我们要找的数字
                max = center - 1
              elif  array[center] < key:
                #这种说明查找到的数字小于我们要找的数字
                min = center + 1
              elif  array[center] == key:
                return ('找到了,在数组的第%s个位置'%center)
    if __name__ == '__main__':
      print (ErFenFa([1,2,3,34,56,57,78,87],87))