Python实现二分查找算法实例

   本文实例讲述了Python实现二分查找算法的方法。分享给大家供大家参考。具体实现方法如下:

  ?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#!/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:
print mid
return mid
print -1
return -1
if __name__ == "__main__":
a = [int(i) for i in list(sys.argv[1])]
m = int(sys.argv[2])
search2(a,m)

  运行:

  administrator@ubuntu:~/Python$ python test_search2.py 123456789 4

  3

  注:

  1.'__':由于python的类成员都是公有、公开的被存取public,缺少像正统面向对象语言的私有private属性。

  于是就用__来将就一下,模拟私有属性。这些__属性往往是内部使用,通常情况下不用改写。也不用读取。

  加上2个下划线的目的,一是不和普通公有属性重名冲突,二是不让对象的使用者(非开发者)随意使用。

  2.__name__ == "__main__"表示程序脚本是直接被执行的.

  如果不等于表示脚本是被其他程序用import引入的.则其__name__属性被设为模块名

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

时间: 2024-09-14 10:47:06

Python实现二分查找算法实例的相关文章

Java实现二分查找算法实例分析_java

本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合

PHP二分查找算法示例【递归与非递归方法】_php技巧

本文实例讲述了PHP二分查找算法.分享给大家供大家参考,具体如下: binarySearch 二分查找采用的方法比较容易理解,以数组为例: ① 先取数组中间的值floor((low+top)/2), ② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作:若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9

JavaScript使用二分查找算法在数组中查找数据的方法_javascript技巧

本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一

[算法]二分查找算法

[思想] 二分搜索主要解决的问题是确定排序后的数组x[0,n-1]中是否包含目标元素target. 二分搜索通过持续跟踪数组中包含元素target的范围(如果target存在数组中的话)来解决问题. 一开始,这个范围是整个数组,然后通过将target与数组中的中间项进行比较并抛弃一半的范围来缩小范围.该过程持续进行, 直到在数组中找到target或确定包含target的范围为空时为止.在有n个元素的表中,二分搜索大约需要执行lgn次比较操作. 提供充足的时间,竟然只有10%的专业程序员能够将这个

使用PHP实现二分查找算法代码分享

第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

二分查找算法及其变种

前言 二分查找算法也称为折半查找算法,是一种在查找算法中普遍使用的算法.其算法的基本思想是:在有序表中,取中间的记录作为比较关键字,若给定值与中间记录的关键字相等,则查找成功:若给定的值小于中间记录的关键字,则在中间记录的左半区间继续查找:若给定值大于中间记录的关键字,则在中间记录的右半区间继续查找:不断重复这个过程,直到查找成功.否则查找失败.这个思想与孔子中的中庸思想和相似. 二分查找算法的实现 基于上述的思想,可以很快写出如下代码: public int binarySearch(int[

90%的程序员无法正确实现二分查找算法???

     前言            ProgrammingPearls(<编程珠玑>)一书的作者Jon Bentley曾经说过类似的话:"90%的程序员无法正确实现二分查找算法..."      言下之意,只有1/10的程序员能够写出"二分查找算法"来.昨天我突然又看到了这句话,于是就随时打开eclipse写下了,还算顺利. 关于"二分查找算法" "二分查找算法",很多地方也被称作是"折半查找"

使用PHP实现二分查找算法代码分享_php技巧

第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

一个经典的二分查找算法的Bug

1:     binarySearch([] a, key) {2:         low = 0;3:         high = a.length - 1;4: 5:         (low <= high) {6:             mid = (low + high) / 2;7:             midVal = a[mid];8:9:             (midVal < key)10:                 low = mid + 1;11: