数据查找是基础的计算机编程工作,而且人们对它的研究已经很多年了。有两种对列表内数据进行查找的方法:顺序查找和二叉查找。当数据项在列表内随机排列的时候可以使用顺序查找,而当数据项在列表内有序排列的时候则会用到二叉查找。
1.顺序查找算法。最突出的查找类型就是从记录集的开始处顺次遍历每条记录,直到找到所要的记录或者是到达数据集的末尾。这就是所谓的顺序查找。顺序查找(也被称为线性查找)是非常容易实现的。从数组的起始处开始,把每个访问到的数组元素依次和所要查找的数值进行比较。如果找到匹配的数据项,就结束查找操作。如果遍历到数组的末尾仍没有产生匹配,那么就说明此数值不在数组内。下面是一个执行顺序查找操作的函数
bool SeqSearch(int[] arr, int sValue)
{
for (int index = 0; index < arr.Length ; index++) //小bug
if (arr[index] == sValue)
return true;
return false;
}
如果发现匹配,那么函数会立刻返回True 并且退出。如果到达数组的末尾,函数还没有返回True,那么要查找的数值就不在数组内,而函数则会返回False。
2.二叉查找算法。当要查找的记录从头到尾都是有序排列的时候,为找到数值可以执行一种比顺序查找更加有效的查找。这种查找被称为是二叉查找。为了理解二叉查找的工作原理,请假设你正试图猜测由朋友选定的一个在1 至100 之间的数字。对于每次你所做的猜测,朋友都会告诉你是猜对了,还是猜大了,或是猜小了。最好的策略是第一次猜50。如果猜大了,那么就应该再猜25。如果猜50 猜小了,则应该再猜75。在每次猜测的时候,你都应该根据调整的数的较小或较大范围(这依赖于你猜测的数是偏大还是偏小)选择一个新的中间点作为下次要猜测的数。只要遵循这个策略,你最终一定会猜出正确的数。
int RbinSearch(int value, int lower, int upper)
{
if (lower > upper)
return -1;
else
{
int mid;
mid = (int)(upper+lower) / 2;
if (value < arr[mid])
return RbinSearch(value, lower, mid - 1);
else if (value == arr[mid])
return mid;
else
return RbinSearch(value, mid + 1, upper);
}
}
查找数据集合内的数值是一种随处可见的计算机操作。最简单的查找数据集合的方法是从数据集合的头部开始查找数据项,直到查找到该数据项或者执行到数据集合的末尾才结束。这种查找方法最好用在数据集合相对较小且无序的时候。如果数据集合是有序排列的,那么二叉查找算法会是一种较好的选择。二叉查找会持续划分数据集合直到找到所要查找的数据项为止。大家可以采用迭代方式或递归方式编写二叉查找算法。C#语言的Array 类包括有内置的二叉查找方法。在调用二叉查找的任何时候都应该可以使用此方法。
分享到:
相关推荐
本书分为8章,第1章介绍了数据结构和算法的基本概念及本书用到的数学和C#的知识;第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;...
第二天 平衡二叉树 6天通吃树结构—— 第一天 二叉查找树 算法速成系列(15)算法系列15天速成——第十五天 图【下】(大结局) 算法系列15天速成——第十四天 图【上】 算法系列15天速成——第十三天 树操作【下】 ...
编者在写这本书时遇到了两个问题...本书所有的数据结构和算法都是用C#语言进行描述,并在相应章节的末尾介绍了在.NET框架中常用的数据结构和算法。用C#在.NET平台开发的技术人员可以从本书中获得许多有益的知识和技术。
本书分为8章,第1章介绍了数据结构和算法的基本概念及本书用到的数学和C#的知识;第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;...
1.1.1 学习数据结构的必要性...1 1.1.2 基本概念和术语...............1 1.2 算法...4 1.2.1算法的特性............................4 1.2.2算法的评价标准....................5 1.2.3算法的时间复杂度...............
本书分为8章,第1章介绍了数据结构和算法的基本概念及本书用到的数学和C#的知识;第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;...
本书分为8章,第1章介绍了数据结构和算法的基本概念及本书用到的数学和C#的知识;第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;...
1.1.1 学习数据结构的必要性...................................................................................1 1.1.2 基本概念和术语........................................................................
1.1.1 学习数据结构的必要性...................................................................................1 1.1.2 基本概念和术语......................................................................
1.1.1 学习数据结构的必要性...................................................................................1 1.1.2 基本概念和术语........................................................................
《Java常用算法手册》旨在帮助Java语言初级程序员深入了解Java算法思想,提升其语言代码编程能力,还可以作为大中专院校学生学习数据结构和算法的参考书,也可为教师授课提供素材,同时还可以作为具有一定编程经验...
本书分为8章,第1章介绍了数据结构和算法的基本概念及本书用到的数学和C#的知识;第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;...
本书旨在帮助Java语言初级程序员深入了解ava算法思想,提升其语言代码编程能力,还可以作为大中专院校学生学习数据结构和算法的参考书,也可为教师授课提供素材,同时还可以作为具有一定编程经验的程序员的参考用书。
数据结构 和 算法 的时候记录的一些笔记。 日常刷题的代码以及思路逻辑。 会不断完善各式算法的问题,完成详情见 和 。 ps : 目前题库为LeetCode,一般一道题会给出多种方案,并且分析记录利弊(时间/空间复杂度)。 ...
全书分6篇共25章,主要内容有C#开发环境的使用、C#语言基础应用、字符串处理技术、数组和集合的使用、面向对象编程技术、数据结构与算法、Windows窗体基础、特色窗体界面、窗体控制技术、MDI窗体和继承窗体、Windows...
5.4 数据结构中的查找算法 145 5.4.1 顺序表结构中的查找算法 145 5.4.2 链表结构中的查找算法 148 5.4.3 树结构中的查找算法 151 5.4.4 图结构中的查找算法 152 5.5 小结 153 第6章 基本数学问题 154 6.1 ...
算法与数据结构辅导 - 2018 年 5 月 - 6 月 两周 2018 年夏季活动的 100 个难级算法 力码Julia Leetcode 算法实践 2015 HackerrankJulia 我参加了20多场比赛,获得了一枚金牌、两枚银牌、八枚铜牌。 征服 Leetcode ...