数据结构-二分法查找

标签: 数据结构 二分法 | 发表时间:2014-01-13 15:40 | 作者:loryshi
出处:http://www.iteye.com

1、二分查找(Binary Search)
     二分查找又称折半查找,它是一种效率较高的查找方法。
     二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。

2、二分查找的基本思想
     二分查找的基本思想是:(设R[low..high]是当前的查找区间)
 (1)首先确定该区间的中点位置:
                 
 (2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下:
     ①若R[mid].key>K,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]。
     ②类似地,若R[mid].key
     因此,从初始的查找区间R[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。

 

 

public static int binarySearch(int[] a, int key) {
2:         int low = 0;
3:         int high = a.length - 1;
4: 
5:         while (low <= high) {
6:             int mid = (low + high) / 2;
7:             int midVal = a[mid];
8:
9:             if (midVal < key)
10:                 low = mid + 1;
11:             else if (midVal > key)
12:                 high = mid - 1;
13:             else
14:                 return mid;    // key found
15:         }
16:         return -(low + 1);     // key not found.
17:     }


已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [数据结构 二分法] 推荐:

数据结构-二分法查找

- - 操作系统 - ITeye博客
1、二分查找(Binary Search).      二分查找又称折半查找,它是一种效率较高的查找方法.      二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构. 2、二分查找的基本思想.      二分查找的基本思想是:(设R[low..high]是当前的查找区间).

数据结构之BloomFilter

- - 编程语言 - ITeye博客
BloomFilter是什么.        BloomFilter主要提供两种操作: add()和contains(),作用分别是将元素加入其中以及判断一个元素是否在其中,类似于Java中的Set接口,它内部采用的byte数组来节 省空间. 其独特之处在于contains()方法,当我们需要查询某个元素是否包含在BloomFilter中时,如果返回true,结果可能是不正确 的,也就是元素也有可能不在其中;但是如果返回的是false,那么元素一定不在其中.

使用graphviz画数据结构

- 王者自由 - Emacs中文网
今天下午用了些时间写了个小的函数,该函数配合 autoinsert + graphviz-dot-mode ,可以很方便的将 C 语言中指定的 struct 结构画出来. 这样,画了多个数据结构之后,再手动添加几条线, 数据结构之间的关系就一目了然了. 1.2 Graphviz 的安装. 1.3 Graphviz 的使用.

数据结构之红黑树

- Shengbin - 董的博客
红黑树是一种自平衡二叉查找树. 它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用. 在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及对set操作的支持).

redis数据结构缓存运用

- - 企业架构 - ITeye博客
之前redis已经描述了redis 的基本作用与用处, 这一篇主要讲述redis运用场景以及分片,和spring整合. redis 存储数据结构大致5种,String 普通键值对,用的比较多. HASH针对 key 唯一标识 hashmap 键值对运用也比较多 list set 当然是集合运用 sortedSet 排序集合使用.

可视化的数据结构和算法

- greenar - 酷壳 - CoolShell.cn
还记得之前发布过的那个关于可视化排序的文章吗. 在网上又看到了一个旧金山大学David Galles做的各种可视化的数据结构和基本算法的主页,网址在这里,大家可以看看. 我把这个页面的目录列在下面并翻译了一下,大家可以直接点击了. 不知道国内的教育有没有相关的教学课件,至少在我大学的时候是没有的. Queues队列: 数组实现.

为什么要学习算法和数据结构

- snowflip - TopLanguage Google Group

MySQL索引背后的数据结构及算法原理

- Mike - 博客园-EricZhang&#39;s Technology Blog
在编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”,我个人是不太赞同这句话(因为我觉得程序不仅仅是数据结构加算法),但是在日常的学习和工作中我确认深深感受到数据结构和算法的重要性,很多东西,如果你愿意稍稍往深处挖一点,那么扑面而来的一定是各种数据结构和算法知识. 例如几乎每个程序员都要打交道的数据库,如果仅仅是用来存个数据、建建表、建建索引、做做增删改查,那么也许觉得数据结构和这东西没什么关系.

Data Structure Visualizations: 数据结构及算法可视化工具

- tiger - 黑客志
Data Structure Visualizations是旧金山大学的David Galles开发的一个以可视化方式演示数据结构和算法的非常棒的工具,可以很好的帮助你理解这些抽象的数据结构和算法,不管你是需要应付考试的CS学生,还是需要对付一些公司的变态面试题的上班族,你都会发现这是一个非常有用的工具,并且这个工具同时提供Java,Flash,以及基于HTML5的Web版本.