- 浏览: 986565 次
- 性别:
- 来自: 杭州
文章分类
- 全部博客 (826)
- 硬件 (8)
- 软件 (24)
- 软件工程 (34)
- JAVA (229)
- C/C++/C# (77)
- JavaScript (8)
- PHP (1)
- Ruby (3)
- MySQL (14)
- 数据库 (19)
- 心情记事 (12)
- 团队管理 (19)
- Hadoop (1)
- spring (22)
- mybatis(ibatis) (7)
- tomcat (16)
- velocity (0)
- 系统架构 (6)
- JMX (8)
- proxool (1)
- 开发工具 (16)
- python (10)
- JVM (27)
- servlet (5)
- JMS (26)
- ant (2)
- 设计模式 (5)
- 智力题 (2)
- 面试题收集 (1)
- 孙子兵法 (16)
- 测试 (1)
- 数据结构 (7)
- 算法 (22)
- Android (11)
- 汽车驾驶 (1)
- lucene (1)
- memcache (12)
- 技术架构 (7)
- OTP-Erlang (7)
- memcached (17)
- redis (20)
- 浏览器插件 (3)
- sqlite (3)
- Heritrix (9)
- Java线程 (1)
- scala (0)
- Mina (6)
- 汇编 (2)
- Netty (15)
- libevent (0)
- CentOS (12)
- mongod (5)
- mac os (0)
最新评论
-
kingasdfg:
你这里面存在一个错误添加多个任务 应该是这样的 /** * ...
Quartz的任务的临时启动和暂停和恢复【转】 -
kyzeng:
纠正一个错误,long型对应的符号是J,不是L。
Jni中C++和Java的参数传递 -
zhaohaolin:
抱歉,兄弟,只是留下作记录,方便学习,如果觉得资料不好,可以到 ...
netty的个人使用心得【转】 -
cccoooccooco:
谢谢!自己一直以为虚机得使用网线才可以与主机连接呢。。
主机网卡无网线连接与虚拟机通信 -
yuqilin001:
要转别人的东西,请转清楚点嘛,少了这么多类,误人子弟
netty的个人使用心得【转】
二分查找又称折半查找,它是一种效率较高的查找方法。
【二分查找要求】:1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。
【算法思想】首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。
重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
【算法复杂度】假设其数组长度为n,其算法复杂度为o(log(n))
下面提供一段二分查找实现的伪代码:
BinarySearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
return mid
elseif mid >des then
max=mid-1
else
min=mid+1
return max
折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下 用O(log n)完成搜索任务。它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如 果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右 半部继续搜索x。
public class BinarySearch { public static void main(String[] args) { int[] ints = { 2, 23, 53, 64, 158, 221, 260, 278, 651, 1564, 2355 }; System.out.println("the position is:" + new BinarySearch().find(ints, 651)); } public int find(int[] values, int key) { int lowerBound = 0; int upperBound = values.length - 1; int curIn; while (true) { curIn = (lowerBound + upperBound) / 2; if (values[curIn] == key) { return curIn; } else if (lowerBound > upperBound) { return values.length; } if (values[curIn] < key) { lowerBound = curIn + 1; } else { upperBound = curIn - 1; } } } }
发表评论
-
一致性 hash 算法( consistent hashing )<转>
2013-05-23 23:53 833consistent hashing 算法早在 1997 年 ... -
【转】几种经典的hash算法
2013-05-23 23:51 3455文章出处:http://hunteagl ... -
常用hash算法及评测[转]
2013-05-23 23:27 1064RS hash 算法 unsigned int RSHas ... -
在Linux上开发网络服务器的一些相关细节:poll与epoll(转)
2011-05-04 16:23 1086随 ... -
Hash算法大全(java实现)【转】
2011-04-16 13:40 1024Hash算法有很多很多种类。具体的可以参考之前我写的Hash算 ... -
打造最快的Hash表[转]
2011-04-16 00:58 787打造最快的Hash表(暴雪用的MPQ文件) ... -
打造最快的Hash表(和Blizzard的对话)[转]
2011-04-16 00:57 839開元最近学习了一下Blizzard的MPQ文件格式,颇有 ... -
哈希算法(Hash Algorithm)初探[转载]
2011-04-16 00:35 1120不约而同的,几乎所有的流行的hash map都采用了DJB h ... -
暴雪的哈希算法 - [转载]
2011-04-16 00:28 839暴雪公司有个经典的字 ... -
哈希算法
2011-04-15 23:37 902哈希算法将任意长度的 ... -
三种简单排序算法及其对比
2011-04-01 13:32 857三种简单排序算法及其对比 代码: class ... -
递归算法
2011-04-01 13:28 975用三角数字问题说明递归 Int triangle(int ... -
高级排序
2011-04-01 13:27 775希尔排序: 插入排序的缺点是复制的次数太多,如果数据开始 ... -
冒泡排序算法的JAVA实现
2011-04-01 13:25 701package Utils.Sort; ... -
常用的各种排序算法的JAVA实现
2011-04-01 13:24 823用JAVA把《Data Structure a ... -
快速排序算法的JAVA实现
2011-04-01 13:23 700package Utils.Sort; / ... -
希尔排序算法的JAVA实现
2011-04-01 13:21 816package Utils.Sort; / ... -
插入排序算法的JAVA实现
2011-04-01 13:21 1038package Utils.Sort; / ... -
选择排序算法的JAVA实现
2011-04-01 13:19 684package Utils.Sort; / ... -
归并排序算法的JAVA实现
2011-04-01 13:18 810package Utils.Sort; / ...
相关推荐
分治法实现二分查找算法实现 分治法实现二分查找算法实现 分治法实现二分查找算法实现
算法分析与设计-实验二 二分查找实验报告
二分查找算法是运用分治的典型例子:给定已按升序排好序的n个元素a[0:n-1],现要在这n个元素中找出一特定元素x。所以容易设计出二分搜索算法:在 a[0] [1] [n-1] 中搜索 x, 找到x时返回其在数组中的位置,否则返回-...
一、实验目的: 熟悉各种查找算法及其复杂性,能够根据实际情况选择合适的存储结构。 二、实验要求: 1、掌握查找的基本方法。 2、提交实验报告,报告...编程分别对有序顺序表的顺序查找,二分查找算法进行实现。
用类汇编语言实现二分查找算法,用windLx 进行相关性分析。
数据结构中简单的二分查找(折半查找)流程图实例
一种改进的二分查找,对传统二分查找进行深度分析,找到新的突破口
主要介绍了Java实现二分查找算法,实例分析了二分查找算法的原理与相关实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下
讲述了数据结构中的几种查找算法,比如二分查找算法等,分析了其平均长度,时间以及空间开销
这个是二分检索的递归实现 具体的进去看看 有注释
安徽大学本科课程《算法设计与分析》实验二《二分查找算法BinarySearch》,包括.m文件和实验报告。
主要介绍了js实现的二分查找算法,结合实例形式较为详细的分析了JavaScript简单实现二分查找算法的运算原理与具体步骤,需要的朋友可以参考下
用C++实现的二分搜索,改写了算法设计与分析课后的题目。按照《算法分析与设计》书上的例题的算法实现的。采用了分治法的思想。
主要介绍了二分查找算法与相关的Python实现示例,Binary Search同时也是算法学习当中最基础的知识,需要的朋友可以参考下
静态查找和动态查找 内查找和外查找 顺序查找又称线性查找(Sequential Search) 二叉查找算法:二分查找又称折半查找(Binary Search)
[7.2.1]--502二分查找算法及分析.srt
[7.2.1]--502二分查找算法及分析.mp4
主要介绍了PHP实现的二分查找算法,结合实例形式分析了二分查找算法的原理与循环、递归等实现技巧,需要的朋友可以参考下
分治法解决棋盘覆盖与二分查找问题,C++描述.算法设计与分析经典例题
实现二分查找的一个demo,有兴趣的下载哦,哈哈 具体分析 在我的博文 数据结构-算法练习 20