顺序查找算法和折半(二分法)查找算法,C语言查找算法详解
查找是指在大量的信息中寻找一个特定的信息。在计算机中,查找是非常重要的一个应用,比如“百度”。查找算法的好坏直接影响查找的速度。
常用的查找算法主要有顺序查找和折半(二分法)查找:
现实编程中,数据一般都是有序的。即使刚开始是无序的,但存储到数据库中时都是先将它们排好序然后再放进去,这样在实际应用中才能更方便。
请输入一个数字:7
下标 = 21
请输入一个数字:58
sorry
1) 先定义一个变量 key 用于存放要查找的 243:
下面再来怎么查找 78:
1) key=78,mid=(low+high)/2=(0+7)/2=3。
2) 此时 a[3]=90,而 key<90,说明 78 在 90 的左边,则往前查找:
若所查找的在数据序列中没有呢?比如查找 123:
1) key=123,mid=(low+high)/2=(0+7)/2=3。
2) 此时 a[3]=90,而 key>90,说明 123 在 90 的左边,则往后查找:
下面将这个程序写下来:
请输入您想查找的数:78
下标 = 2
请输入您想查找的数:123
sorry, data is not found
折半查找在每次查找时都排除了一半数据,所以它的效率是非常高的。顺序查找的平均查找长度为
但是,折半查找只适合数组,不适合链表。链表中也可以用折半查找,但是不仅不会提高效率,反而还会降低效率。因为数组可以通过下标直接找到 low、mid 和 high 对应的元素,而链表是通过指针连接起来的不连续的链,所以若要查找 low、mid 和 high 对应的元素,每次都要从第一个结点出发一个一个往后找。所以一般不在链表内使用折半查找。
常用的查找算法主要有顺序查找和折半(二分法)查找:
- 顺序查找是指从数组的一端开始逐个进行比较,直到找到该数据为止。
- 折半查找是指在已经排好序的一组数据中快速查找数据。
现实编程中,数据一般都是有序的。即使刚开始是无序的,但存储到数据库中时都是先将它们排好序然后再放进去,这样在实际应用中才能更方便。
顺序查找
查找数组 a 中第一次出现数字 m 的下标并输出该下标,如果没有则输出“sorry”,实现代码如下:# include <stdio.h> int main(void) { int a[] = {1,5,66,8,55,9,1,32,5,65,4,8,5,15,64,156,1564,15,1,8,9,7,215, 16,45,5,6,164,15,236,2,5,55,6,4,1,59,23,4,5,314,56,15,3,54, 1,54,54,2,4,4,5,15,698,486,56,26,98,78,456,1894,564,26,56,5}; int n; //存放数组a中元素的个数 int m; //查找的数字 int i; //循环变量 n = sizeof(a) / sizeof(int); //求出数组中所有元素的个数 printf("请输入一个数字:"); scanf("%d", &m); for (i=0; i<n; ++i) { if (a[i] == m) { printf("下标 = %d\n", i); break; } } if (i == n) { printf("sorry\n"); } return 0; }输出结果是:
请输入一个数字:7
下标 = 21
请输入一个数字:58
sorry
折半查找
折半查找是很有意思的,它的算法复杂度非常低,但它要求数据必须是已经排好序的。比如数组 a 中:13 45 78 90 127 189 243 355
现在看看怎么用折半算法在其中查找 243。1) 先定义一个变量 key 用于存放要查找的 243:
key = 243
2) 定义变量 low、mid和high 分别存储数组的最小下标、中间下标和最大下标。并有:mid = (low+high)/2 = (0+7)/2 = 3
3) 此时 a[3]=90,而 key>90,说明 243 在 90 的右边,则往后查找:low = mid + 1 = 4
4) 然后重新更新 mid:mid = (4+7)/2 = 5
5) 此时 a[5]=189,而 key>189,说明 243 在 189 的右边,继续往后查找:low = mid+1 = 6
6) 然后重新更新 mid:mid = (6+7)/2 = 6
7) 此时 a[6]=key=243,找到了。下面再来怎么查找 78:
1) key=78,mid=(low+high)/2=(0+7)/2=3。
2) 此时 a[3]=90,而 key<90,说明 78 在 90 的左边,则往前查找:
high = mid-1 = 2
3) 然后重新更新 mid:mid = (0+2)/2 = 1
4) 此时 a[1]=45,而 key>45,说明 78 在 45 的右边,则往后查找:low = 1+1 = 2
5) 然后重新更新 mid:mid = (2+2)/2 = 2
6) 此时 a[2]=key=78,就找到了。若所查找的在数据序列中没有呢?比如查找 123:
1) key=123,mid=(low+high)/2=(0+7)/2=3。
2) 此时 a[3]=90,而 key>90,说明 123 在 90 的左边,则往后查找:
low = mid+1 = 4
3) 然后重新更新 mid:mid = (4+7)/2 = 5
4) 此时 a[5]=189,而 key<189,说明 123 在 189 的左边,则往前查找:high=mid-1=4。
5) 此时 low==high,如果该数仍不是要找的数的话,说明该序列中就没有该数了。下面将这个程序写下来:
# include <stdio.h> int main(void) { int a[] = {13, 45, 78, 90, 127, 189, 243, 355}; int key; //存放要查找的数 int low = 0; int high = sizeof(a)/sizeof(a[0]) - 1; int mid; int flag = 0; //标志位, 用于判断是否存在要找的数 printf("请输入您想查找的数:"); scanf("%d", &key); while ((low <= high)) { mid = (low + high) / 2; if (key < a[mid]) { high = mid - 1; } else if (a[mid] < key) { low = mid +1; } else { printf("下标 = %d\n", mid); flag = 1; break; } } if (0 == flag) { printf("sorry, data is not found\n"); } return 0; }输出结果是:
请输入您想查找的数:78
下标 = 2
请输入您想查找的数:123
sorry, data is not found
折半查找在每次查找时都排除了一半数据,所以它的效率是非常高的。顺序查找的平均查找长度为
n+1/2
,而折半查找的平均查找长度为 log2(n+1)-1。可见使用折半查找时,数据数量越多查找效率就越高。但是,折半查找只适合数组,不适合链表。链表中也可以用折半查找,但是不仅不会提高效率,反而还会降低效率。因为数组可以通过下标直接找到 low、mid 和 high 对应的元素,而链表是通过指针连接起来的不连续的链,所以若要查找 low、mid 和 high 对应的元素,每次都要从第一个结点出发一个一个往后找。所以一般不在链表内使用折半查找。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频