网上看到《五大经典查找》,学习了。原文代码用C#,这里用java,顺便对照一下两种语言的语法。
在我们的生活中,无处不存在着查找,比如找一下班里哪个mm最pl,猜一猜mm的芳龄....... 对的这些都是查找。
在我们的算法中,有一种叫做线性查找。
分为:顺序查找。
折半查找。
查找有两种形态:
分为:(1)破坏性查找
比如有一群mm,我猜她们的年龄,第一位猜到了是23+,此时这位mm已经从我脑海里面的mmlist中remove掉了。哥不找23+的,所以此种查找破坏了原来的结构。
(2)非破坏性查找, 这种就反之了,不破坏结构。
一、顺序查找:
这种非常简单,就是过一下数组,一个一个的比,找到为止。
-
import
java.util.List;
-
import
java.util.ArrayList;
-
import
java.util.Arrays;
-
public
class
Program{
-
public
static
void
main(String[] args){
-
-
-
Integer a[]={2
,
3
,
5
,
8
,
7
};
-
List<Integer> list=Arrays.asList(a);
-
int
result = SequenceSearch(list,
3
);
-
if
(result != -
1
)
-
System.out.println("3 已经在数组中找到,索引位置为:"
+ result);
-
else
-
System.out.println("呜呜,没有找到!"
);
-
-
}
-
-
-
public
static
int
SequenceSearch(List<Integer> list,
int
key){
-
for
(
int
i =
0
; i < list.size(); i++) {
-
-
if
(key == list.get(i))
-
return
i;
-
}
-
-
return
-
1
;
-
}
-
-
}
程序运行:
C:\java>java Program
3 已经在数组中找到,索引位置为:1
二、折半查找:
这种查找很有意思,就是每次都砍掉一半,比如"幸运52“中的猜价格游戏,价格在999元以下,1分钟之内能猜到几样给几样,如果那些选手都知道折半查找,那结果是相当的啊。
不过要注意,这种查找有两个缺点:
第一: 数组必须有序,不是有序就必须让其有序,大家也知道最快的排序也是NLogN的,所以.....呜呜。
第二: 这种查找只限于线性的顺序存储结构。
上代码:
-
import
java.util.*;
-
public
class
BSearch{
-
public
static
void
main(String[] args)
-
{
-
Integer a[]={ 3
,
7
,
9
,
10
,
11
,
24
,
45
,
66
,
77
};
-
List<Integer> list=Arrays.asList(a);
-
-
-
int
result = BinarySearch(list,
45
);
-
-
if
(result != -
1
)
-
System.out.println("45 已经在数组中找到,索引位置为:"
+ result);
-
else
-
System.out.println("呜呜,没有找到!"
);
-
-
-
}
-
-
-
-
public
static
int
BinarySearch(List<Integer> list,
int
key)
-
{
-
-
int
low =
0
;
-
-
-
int
high = list.size() -
1
;
-
-
while
(low <= high)
-
{
-
-
int
middle = (low + high) /
2
;
-
-
if
(list.get(middle) == key){
-
return
middle;
-
} else
if
(list.get(middle) > key){
-
-
high = middle - 1
;
-
}else
{
-
-
low = middle + 1
;
-
}
-
}
-
-
return
-
1
;
-
}
-
-
}
程序运行:
C:\java>java BSearch
45 已经在数组中找到,索引位置为:6
先前也说过,查找有一种形态是破坏性的,那么对于线性结构的数据来说很悲惨,因为每次破坏一下,
可能都导致数组元素的整体前移或后移。
所以线性结构的查找不适合做破坏性操作,那么有其他的方法能解决吗?嗯,肯定有的,不过要等下一天分享。
ps: 线性查找时间复杂度:O(n);
折半无序(用快排活堆排)的时间复杂度:O(NlogN)+O(logN);
折半有序的时间复杂度:O(logN);
分享到:
相关推荐
又叫做线性查找,是查找算法中最基本的查找,它的过程是:从表中第一个(或最后一个)记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和给定值相等,则查找成功,找到所查的记录;如果直到最后一个...
——线性查找 目录 课程导入 1 理解数据查找操作的概念 2 知道数据查找操作的两种方法 3 能正确理解线性查找方法 4 会正确应用线性查找方法,解决实际问题 淘宝搜索自己想要购买的商品; 借书搜索书籍名称。 数据...
3. 递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。 4. 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。 5. 若i==k,返回x;若i,在...
线性查找 二分查找算法的mfc代码 1)动态生成自定义大小的数组,并以随机数初始化数组。 2)随机产生查找数据 3)按“开始”菜单演示查找过程,按“结束”菜单结束查找演示过程。 4)在客户区正确显示当前查找情况过程。...
枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...
MFC动态演示线性查找和折半查找,分为自动演示和单步演示,单步演示用鼠标左键实现
线性查找又称顺序查找,其基本思想位:从线性表的一端向另一端逐个将记录与给定值进行比较,若相等,则查找成功,给出该记录在表中的位置;若整个表检测完仍未找到与给定值相等的记录,则查找失败,给出失败信息。...
常见的搜索算法包括线性搜索、二分搜索等。 图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是...
提出了一种用于数字全息显微术的可靠度导向快速相位展开算法。...实验中,采用非线性查找表的相位展开算法比传统洪水算法快68倍以上,比枝切法快近3倍。结果表明,该算法在保持高质量相位展开的情况下大大提高了速度。
顺序查找:线性查找,从表的第一个逐个开始和待查找元素比较,直到最后一个(暴力破解) //C //a为待查数组,n为待查数组长度,key为待查找值 int Sequential_Search(int *a,int n, int key) { int i; for(i=1;i&...
常见的查找算法包括线性查找和二分查找。 线性查找:也称为顺序查找,它从数据集合的第一个元素开始逐个比较,直到找到目标元素或者遍历完整个集合。这种方法简单直观,适用于小型数据集合,但对于大型数据集合效率...
(1)掌握顺序查找,二分法查找和索引查找的算法思想及程序实现方法。 (2)掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现方法。 (3)掌握散列存储结构的思想,能选择合适散列函数,实现...
折半查找 折半查找(又称二分查找)是一种高效的查找算法,适用于已排序的数组或列表。...因此,折半查找比线性查找和冒泡排序等算法更高效。但是,折半查找要求数组必须是有序的,否则无法使用此算法。
数据结构,实验六,递归实验,c语言编程实现
1. (5 分) 欧几里德算法利用算术基本定理 (任何一个正整数去除另一个正整数, 3. (5 分) 求解递归方程,假设 n ≤ 3 时 T(n)为常数,T
1、熟悉线性查找算法。 2、掌握顺序查找、二分查找算法 二、 实验内容: 1. SeqList类中增加下列成员方法: public int lastIndexOf(T key) //返回最后出现的关键字为key元素位置 最终代码: public int IndexOf(T ...
线性查找算法(也称为顺序查找算法)是一种简单的查找算法,用于在给定的数据集中查找特定值。它从数据集的开头开始逐个元素地进行比较,直到找到待查找的元素,或者遍历完整个数据集仍未找到。跳跃搜索算法原理:...
查找问题在计算机科学中是一个经典的问题,包括线性查找、二分查找、哈希查找等多种方法。在实际应用中,查找问题具有广泛的研究和应用价值。 在这份资源中,您将学习到查找问题的定义和性质,以及如何使用Python...
常见的算法包括排序算法(如冒泡排序、插入排序、快速排序)、查找算法(如线性查找、二分查找)、图算法(如深度优先搜索、广度优先搜索)等。 学习数据结构和算法可以帮助您更好地理解和解决问题,提高程序的效率...