二分查找,是一种针对有序序列的查找方式,每次迭代会缩小一半的查找范围,一次查找的时间复杂度为O(logN)。
简单说一下二分查找过程:在有序序列seq[]中找一个数n,假设这个序列的起始下标分别为a,b,mid=(a+b)/2,那么n要么就是seq[mid](n=seq[mid]),要么在mid左边(n<seq[mid]),要么在mid右边(n>seq[mid]),要么这个数根本不在seq[]中。

下面这道题是二分查找的典型应用:
zoj1101
题意描述:在给定整数序列(<=1000)中找出四个不同的数,使得三个数的和等于另外一个数。
直接用四层循环铁定超时,这里采用了一种拿空间换时间的方式。
假设有a+b+d=c,这等价于a+b=c-d,我们可以把所有的a+b存起来(<=10^6个),把所有的c-d也存起来(<=10^6个),当拿到每一个a+b时我们只需要在所有c-d的序列中查找就行了。先把c-d序列排序,排序时间复杂度O(NlogN),查找过程可以用二分,这样就不会超时啦。
以下是本题代码:
posted on 2012-08-01 21:39 小鼠标 阅读(1043) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年7月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

随笔分类(111)

随笔档案(127)

friends

最新评论

  • 1. re: 线段树
  • 是这个样子的,所以在OJ有时候“卡住”了也不要太灰心,没准真的不是自己的原因呢。
    加油,祝你好运啦!
  • --小鼠标
  • 2. re: 线段树
  • 对于编程竞赛来说,Java所需时间一般为C/C++的两倍。合理的竞赛给Java的时间限制是给C/C++的两倍。
  • --伤心的笔
  • 3. re: poj1273--网络流
  • 过来看看你。
  • --achiberx
  • 4. re: (转)ubuntu11.10无法启动无线网络的解决方法
  • 膜拜大神。。查了一个下午资料终于在这里解决了问题。。神牛说的区域赛难道是ACM区域赛。。?
  • --Hang
  • 5. re: 快速排序、线性时间选择
  • 博主,谢谢你的文章。你的方法可以很好的处理分区基准在数组中重复的情况,书上的方法遇到这种输入会堆栈溢出。书上给出了解释但给的方法貌似不简洁。
  • --lsxqw2004

阅读排行榜