Python二分法搜索算法实例分析

yipeiwu_com5年前Python基础

本文实例分析了Python二分法搜索算法。分享给大家供大家参考。具体分析如下:

今天看书时,书上提到二分法虽然道理简单,大家一听就明白但是真正能一次性写出别出错的实现还是比较难的,即使给了你充足的时间,比如1小时。如果你不是特别认真的话,可能还是会出一些这样那样的错误,所以就尝试了自己去实现一下,看能否一次通过,结果自然不言而喻,虽然用的时间不长,但是我失败了,呵呵。

个人觉得失败的最主要原因是自己没有认真的先想好这个思路和可能出现的分支情况,而是直接凭主观臆想就去写代码了,完全正中书上所说的行为,所以也如书上所说,出错了。后经调试应该是得到了基本的正确算法,内容如下:

#!/usr/bin/env python
#encoding: utf-8
def half_search(search_arr, search_str):
  lb = 0
  ub = len(search_arr) - 1
  for i in range(ub/2 + 1):
    if lb > ub:
      return -1
    mid = (ub + lb)/2
    if search_arr[mid] == search_str:
      return mid
    elif search_arr[mid] > search_str:
      ub = mid - 1
    else:
      lb = mid + 1
if __name__=='__main__':
  arr = [10,20,30,40,50,60,70]
  print half_search(arr, 1)
  print half_search(arr, 11)
  print half_search(arr, 22)
  print half_search(arr, 33)
  print half_search(arr, 40)
  print half_search(arr, 55)
  print half_search(arr, 66)
  print half_search(arr, 70)
  print half_search(arr, 8)

结果:

-1 
-1 
-1 
-1 
3 
-1 
-1 
6 
-1

正整数代表在数组中的下标,3那就是第4个位置;-1代表不存在

总结:

实现简单的算法之前,如果已经有了一套最简易的实现【比如直接打印100条相似的内容】,不妨要想想是否还有更精巧的实现【可否用循环+参数化替代】;实现稍微复杂点的算法时,不妨先在纸上画出各种可能的验证情况,避免实现是缺胳膊短腿的;还有一点就是算法什么的还是要多练,不然稍微复杂的过一阵可能就会忘记细节了。我想这就叫术业有专攻吧!

希望本文所述对大家的Python程序设计有所帮助。

相关文章

pandas 层次化索引的实现方法

层次化索引是pandas的一项重要功能,它使你能在一个轴上拥有多个(两个以上)索引级别。 创建一个Series,并用一个由列表或数组组成的列表作为索引。 data=Series(np...

深入理解Python中的*重复运算符

在python中有个特殊的符号“*”,可以用做数值运算的乘法算子,也是用作对象的重复算子,但在作为重复算子使用时一定要注意 注意的是:*重复出来的各对象具有同一个id,也就是指向在内存...

Python基于identicon库创建类似Github上用的头像功能

本文实例讲述了Python基于identicon库创建类似Github上用的头像功能。分享给大家供大家参考,具体如下: Identicon在很多大型IT网站上可以见到,比如Github,...

python实现简单成绩录入系统

学了一个多月的python,做了一个小程序:python实现简单成绩录入系统,实验一下 menu部分 from tkinter import*#这是一个python模块,python...

opencv3/python 鼠标响应操作详解

opencv3/python 鼠标响应操作详解

鼠标回调函数: def setMouseCallback( windowName, #窗口名称 onMouse, #鼠标响应处理函数 param=None)...