- 浏览: 241505 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (127)
- vim (3)
- python (44)
- pymysql (1)
- mysql (9)
- macvim (1)
- erlang (3)
- twisted (0)
- tornado (5)
- django (7)
- postgresql (5)
- sql (1)
- java (7)
- tech (4)
- cache (1)
- lifestyle (3)
- html (1)
- ubuntu (2)
- rabbitmq (1)
- algorithm (8)
- Linux (4)
- Pythonista (1)
- thread (1)
- sort (6)
- 设计模式 (1)
- search (1)
- Unix (6)
- Socket (3)
- C (2)
- web (1)
- gc (1)
- php (10)
- macos (1)
最新评论
-
2057:
这个程序有bug。
查找算法学习之二分查找(Python版本)——BinarySearch -
dotjar:
NB
一个Python程序员的进化[转]
引用
在计算机科学中,折半搜索,也称二分查找算法、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
- 时间复杂度:O(logn)
- 空间复杂度:O(1)
示例:
#!/usr/bin/env python #-*-coding:utf-8-*- def binary_search(l,key,lo=0,hi=None): if not hi: hi = len(l) while lo<hi: mid = (lo+hi)//2 if l[mid]>key: hi = mid-1 elif l[mid]<key: lo = mid+1 else: return mid return -1 def main(): L = [1,2,3,4,5,6] print binary_search(L,6) if __name__=="__main__": main()
参考资料:
http://zh.wikipedia.org/wiki/%E6%8A%98%E5%8D%8A%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95
发表评论
-
macos 10.9.2 clang: error: unknown argument: '-mno-fused-madd' [-Wunused-command
2014-03-25 19:13 1721方法总是有的,当然需要你去寻找。 当然如果花费太多的时间在一件 ... -
PostgreSQL psycopg2:IndexError: tuple index out of range
2014-01-09 17:04 2186Postgresql psycopg2使用like查询的时候 ... -
Python 迭代器和生成器
2013-10-15 23:09 2809迭代器 迭代器只不过是一个实现迭代器协议的容器对象。它基于两个 ... -
Python时间模块
2013-10-15 23:03 3422time模块 时间模块中最常用的一个函数就是获取当前时间的函数 ... -
Python装饰器
2013-10-15 22:59 1508编写自定义装饰器有许多方法,但最简单和最容易理解的方法是编写一 ... -
python list
2013-10-15 22:56 1210简单总结以及整理如下: >>> dir( ... -
Python Excel
2013-09-10 17:21 930安装lib easy_install xlrd def ... -
排序算法学习(python版本)之堆排序(HeapSort)
2013-07-01 22:54 1956Contains: 堆排序以及堆排序的应用 堆排序(Heaps ... -
python range xrange
2013-06-25 23:30 1102引用Help on built-in function ran ... -
python class
2013-06-25 00:54 1785引用类是创建新对象类 ... -
AttributeError: 'module' object has no attribute 'SendCloud'
2013-06-05 11:46 7016网上查了下 意思是说你命名的文件名不能和lib重名,这样会导 ... -
python string
2013-05-07 23:44 2159如果这就是字符串,这本来就是字符串 首先看下字符串的方法 ... -
Python property
2013-03-29 19:56 0由于之前有总结过,可以参考http://2057.iteye. ... -
python tips
2013-03-28 23:57 8451、enum #!/usr/bin/env python ... -
python decorators
2013-03-28 23:36 1323Contains: 1、decorators 2、funct ... -
python closures
2013-03-28 22:09 1148Closure:如果在一个内部函数里,对在外部作用域(但不是在 ... -
Python map、filter,reduce介绍
2013-03-28 22:02 12411、filter(function,iterable) 引用C ... -
Python __new__ 、__init__、 __call__
2013-03-26 23:49 5293Contains: __new__: 创建对象时调用,返回当 ... -
Python socket简介
2013-03-25 23:42 2115自豪地使用dir和help. Python 2.7.2 ( ... -
Tornado ioloop源码简析
2013-03-21 00:18 2798#!/usr/bin/env python #-*-en ...
相关推荐
基于python的查找算法-二分查找Binary Search
二分查找(Binary Search)是一种在有序数组中查找特定元素的算法。该算法的基本思想是先确定待查找区间的中间位置,然后将待查找元素与中间位置元素进行比较,根据比较结果缩小待查找区间的范围,直至找到目标元素...
安徽大学本科课程《算法设计与分析》实验二《二分查找算法BinarySearch》,包括.m文件和实验报告。
//二分查找 #include const int MAXN=10010; using namespace std; //二分查找,递归实现 int binarySearch(int a[],int low,int high,int key) { //查找某元素是否在数组中,若存在,则返回下标,否则...
C 语言中效率最高的查找方式,非常实用。...函数功能: 二分查找 入口参数: 待查找有序表的首地址 int *a 待查找的数据 int num 出口参数: 查找成功返回数据在有序表中的位置0 ~ n-1,不成功返回 -1
主要介绍了二分查找算法与相关的Python实现示例,Binary Search同时也是算法学习当中最基础的知识,需要的朋友可以参考下
Python手撕算法BinaryTree
本文实例讲述了python二分查找算法的递归实现方法。分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while ...
c++ 二分搜索树 二分查找树 binary search tree BST
描述: ...第二行为n(n不超过10000)个整数;第三行为一个整数m(m不超过50000),表示查询的个数;接下来m行每行一个整数k。 输出: 每个查询的输出占一行,如果k在序列中,输出Yes,否则输出No。
使用Python3实现非递归的二分查找算法,资源中包含具体实现代码与单元测试代码,已进行代码重构,代码风格整洁易读
假设有一个人要我们猜0-99之间的一个数,那么最好的方法就是从0-99的中间数49开始猜。 如果要猜的数小于49,就猜24(0-48的中间数);如果要猜的数大于49,就猜74(50-99的中间数)。...二分查找的工作方法就是如此。
课本上的二分查找的实现。有初始化,赋值,搜索三个操作
A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. It makes progressively better guesses, and closes in on the sought value, by comparing an ...
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
C#,数据检索算法之二分搜索(Binary Search)的源代码 数据检索算法是指从数据集合(数组、表、哈希表等)中检索指定的数据项。 数据检索算法是所有算法的基础算法之一。 本文提供 Binary Search 的源代码。
静态查找和动态查找 内查找和外查找 顺序查找又称线性查找(Sequential Search) 二叉查找算法:二分查找又称折半查找(Binary Search)
这是一个用c++做的简单的折半查找算法,在递增的序列数组中,找到对应的数字的位置
s[middle] 关键字小于中值 继续二分查找 并将上限改为middle BinarySearch s x low middle 1 ; else 关键字大于中值 继续二分查找 并将下限改为middle BinarySearch s x middle + 1 high ;">if high < low ...