各种基本算法实现小结(六)—— 查找算法

各种基本算法实现小结(六)—— 查找算法

(均已测试通过)

===================================================================

1、简单查找

在一组无序数列中,查找特定某个数值,并返回其位置pos

测试环境:VC 6.0 (C)

#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX 101 void input(int num[]) { int i; srand((unsigned)time(NULL)); for(i=1; i<MAX; i++) num[i]=rand()%100; } void output(int num[]) { int i; for(i=1; i<MAX; i++) { printf("%5d", num[i]); if(0==i%10) printf("/n"); } } int find(int num[], int x) { int i; for(i=1; i<MAX; i++) if(x == num[i]) return i; return 0; } void main() { int x, pos, num[MAX]; input(num); printf("num...: /n"); output(num); printf("Enter find num: "); scanf("%d", &x); pos=find(num, x); if(pos) printf("OK! %d is found in pos: %d/n", x, pos); else printf("Sorry! %d is not found... in num/n", x); }

运行结果:

==========================================================

2、 折半查找

在有序数列中,逐步缩小查找范围,直至找到或找不到记录为止

本算法首先随机生成100个无序数列,然后利用快速排序算法排序成有序数列,然后再用折半查找算法

说明:本算法中的排序算法,可用上一篇排序算法中的任一种算法实现,如选择排序、冒泡排序、快速排序等

测试环境:VC 6.0 (C)

#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX 101 void input(int num[]) { int i; srand((unsigned)time(NULL)); for(i=1; i<MAX; i++) num[i]=rand()%100; } void output(int num[]) { int i; for(i=1; i<MAX; i++) { printf("%5d", num[i]); if(0==i%10) printf("/n"); } } void sort(int num[], int low, int high) /* quick sort */ { int l, h; if(low<high) { l=low; h=high; num[0]=num[l]; /* save pivot */ while(l<h) { while(l<h && num[h]>=num[0]) h--; num[l]=num[h]; while(l<h && num[l]<=num[0]) l++; num[h]=num[l]; } num[l]=num[0]; /* insert pivot */ sort(num, low, l-1); sort(num, l+1, high); } } int find(int num[], int x, int low, int high) { int mid; while(low<=high) { mid=(low+high)/2; /* find is OK */ if(x==num[mid]) return mid; else if(x<num[mid]) high=mid-1; else low=mid+1; } return 0; } void main() { int x, pos, num[MAX]; input(num); printf("sort before... /n"); output(num); sort(num, 1, MAX-1); printf("sort after... /n"); output(num); printf("Enter find num: "); scanf("%d", &x); pos=find(num, x, 1, MAX-1); if(pos) printf("OK! %d is found in pos: %d/n", x, pos); else printf("Sorry! %d is not found... in num/n", x); }

运行结果:

==========================================================

参考推荐:

学习算法之路

各种基本算法实现小结(一)—— 链 表

各种基本算法实现小结(二)—— 堆 栈

各种基本算法实现小结(三)—— 树与二叉树

各种基本算法实现小结(四)—— 图及其遍历

各种基本算法实现小结(五)—— 排序算法

各种基本算法实现小结(六)—— 查找算法

各种基本算法实现小结(七)—— 常用算法

12个有趣的C语言面试题

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券