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程序设计有所帮助。

赞 (0)

相关推荐

  • python实现数独算法实例

    本文实例讲述了python实现数独算法的方法.分享给大家供大家参考.具体如下: # -*- coding: utf-8 -*- ''' Created on 2012-10-5 @author: Administrator ''' from collections import defaultdict import itertools a = [ [ 0, 7, 0, 0, 0, 0, 0, 0, 0], #0 [ 5, 0, 3, 0, 0, 6, 0, 0, 0], #1 [ 0, 6, 2

  • python选择排序算法实例总结

    本文实例总结了python选择排序算法.分享给大家供大家参考.具体如下: 代码1: def ssort(V): #V is the list to be sorted j = 0 #j is the "current" ordered position, starting with the first one in the list while j != len(V): #this is the replacing that ends when it reaches the end o

  • Python实现LRU算法的2种方法

    LRU:least recently used,最近最少使用算法.它的使用场景是:在有限的空间中存储对象时,当空间满时,会按一定的原则删除原有的对象,常用的原则(算法)有LRU,FIFO,LFU等.在计算机的Cache硬件,以及主存到虚拟内存的页面置换,还有Redis缓存系统中都用到了该算法.我在一次面试和一个笔试时,也遇到过这个问题. LRU的算法是比较简单的,当对key进行访问时(一般有查询,更新,增加,在get()和set()两个方法中实现即可)时,将该key放到队列的最前端(或最后端)就

  • python实现的希尔排序算法实例

    本文实例讲述了python实现希尔排序算法的方法.分享给大家供大家参考.具体如下: def shellSort(items): inc = len(items) / 2 while inc: for i in xrange(len(items)): j = i temp = items[i] while j >= inc and items[j-inc] > temp: items[j] = items[j - inc] j -= inc items[j] = temp inc = inc/2

  • python实现的DES加密算法和3DES加密算法实例

    本文实例讲述了python实现的DES加密算法和3DES加密算法.分享给大家供大家参考.具体实现方法如下: ############################################################################# # Documentation # ############################################################################# # Author: Todd Whitema

  • python插入排序算法实例分析

    本文实例讲述了python插入排序算法.分享给大家供大家参考.具体如下: def insertsort(array): for removed_index in range(1, len(array)): removed_value = array[removed_index] insert_index = removed_index while insert_index > 0 and array[insert_index - 1] > removed_value: array[insert

  • Python实现二分查找算法实例

    本文实例讲述了Python实现二分查找算法的方法.分享给大家供大家参考.具体实现方法如下: #!/usr/bin/env python import sys def search2(a,m): low = 0 high = len(a) - 1 while(low <= high): mid = (low + high)/2 midval = a[mid] if midval < m: low = mid + 1 elif midval > m: high = mid - 1 else:

  • Python实现的最近最少使用算法

    本文实例讲述了Python实现的最近最少使用算法.分享给大家供大家参考.具体如下: # lrucache.py -- a simple LRU (Least-Recently-Used) cache class # Copyright 2004 Evan Prodromou <evan@bad.dynu.ca> # Licensed under the Academic Free License 2.1 # Licensed for ftputil under the revised BSD

  • Python语言实现机器学习的K-近邻算法

    Python语言实现机器学习的K-近邻算法

    写在前面 额...最近开始学习机器学习嘛,网上找到一本关于机器学习的书籍,名字叫做<机器学习实战>.很巧的是,这本书里的算法是用Python语言实现的,刚好之前我学过一些Python基础知识,所以这本书对于我来说,无疑是雪中送炭啊.接下来,我还是给大家讲讲实际的东西吧. 什么是K-近邻算法? 简单的说,K-近邻算法就是采用测量不同特征值之间的距离方法来进行分类.它的工作原理是:存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系

  • python实现马耳可夫链算法实例分析

    本文实例讲述了python实现马耳可夫链算法的方法.分享给大家供大家参考.具体分析如下: 在<程序设计实践>(英文名<The Practice of Programming>)的书中,第三章分别用C语言,C++,AWK和Perl分别实现了马耳可夫链算法,来通过输入的文本,"随机"的生成一些有用的文本. 说明: 1. 程序使用了字典,字典和散列可不是一个东西,字典是键值对的集合,而散列是一种能够常数阶插入,删除,不过可以用散列来实现字典. 2. 字典的setdef

随机推荐