查找——顺序查找和折半查找

2024-06-16 13:36
文章标签 查找 顺序 折半

本文主要是介绍查找——顺序查找和折半查找,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

查找

关于顺序查找和折半查找,可点击此处进入旧金山大学提供的动画演示网站。

顺序查找

​ 顺序查找又称线性查找。它对于顺序表和链表都是适用的。对于顺序表,可通过数组下标递增来顺序扫描每个元素;对于链表,则通过指针next来依次扫描每个元素。

​ 本次顺序表用指针,也就是申请一个堆空间,使用方式和数组还是一致。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>typedef int ElemType;
typedef struct {// 整型指针ElemType *elem;// 存储动态数组里面元素的个数int table_len;
} SSTable;/** 顺序表初始化*/
void st_init(SSTable &ST, int len) {// 多申请一个位置用来存哨兵ST.table_len = len + 1;ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.table_len);// 筛子srand(time(NULL));// 随机数生成数据for (int i = 1; i < ST.table_len; i++) {// 生产的数字都在0-99中间ST.elem[i] = rand() % 100;}
}/** 打印顺序表*/
void st_print(SSTable ST) {for (int i = 1; i< ST.table_len; i++) {printf("%3d", ST.elem[i]);}printf("\n");
}/** 查找元素位置*/
int search_seq(SSTable ST, ElemType key) {// 零号元素作为哨兵// 遍历数组时 可以少写一个 i >= 0 的判断ST.elem[0] = key;int i;// 从后往前找// 如果找到 i刚好是对应的位置for (i = ST.table_len - 1; ST.elem[i] != key; i--);return i;
}int main() {SSTable ST;// 一、顺序表初始化st_init(ST, 10);// 二、打印顺序表st_print(ST);// 存储元素ElemType key;printf("please input search key:\n");scanf("%d", &key);// 元素存储位置int pos;pos = search_seq(ST, key);if (pos) {printf("search elem success, location: %d\n", pos);} else {printf("search elem failed\n");}return 0;
}

折半查找

​ 折半查找又称为二分查找,它仅适用于有序的顺序表。

折半查找的基本思想:首先将给定值key与表中间位置的元素比较。若相等,则查找成功,返回该元素的存储位置。若不等,则所需要查找的元素只能在中间元素以外的前半部分或后半部分(例如:在查找表升序排列时,若给定值key大于中间元素,则查找的元素只可能在后半部分),然后再缩小的范围内继续进行同样的查找,如此重复,直到找到为止。或确定表中没有所需要查找的元素,则查找不成功,返回查找失败的信息。

​ 针对顺序表有序,使用 qsort 来排序, qsort 的使用方法如下:

#include <stdlib.h>void qsort(void *buf, size_t num, size_t size, int (*compare)(const void*, const void*));
  • buf:要排序数组的起始地址,也可以是指针,申请了一块连续的堆空间。
  • num:数组中元素的个数。
  • size:数组中每个元素所占用的空间大小。
  • compare:比较规则,需要我们传递一个函数名,这个函数由我们自己编写,返回值必须是 int 类型,形参是两个 void 类型指针,这个函数我们编写,但是由qsort内部调用,相当于我们传递一种行为给qsort。

折半查找不需要用到哨兵,因此不要受上一节顺序查找的影响,代码实战流程是:

  1. 我们初始化顺序表,随机10个元素。
  2. 使用 qsort 进行排序,排序完毕后,打印。
  3. 输入要查找的元素值,存入变量 key 中。
  4. 通过二分查找查找对应 key 值,找到则输入在顺序表中的位置,没找到输出未找到。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>typedef int ElemType;
typedef struct {// 整型指针ElemType *elem;// 存储动态数组里面元素的个数int table_len;
} SSTable;/** 顺序表初始化*/
void st_init(SSTable &ST, int len) {// 折半查找不使用0号位置作为哨兵ST.table_len = len;ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.table_len);// 筛子srand(time(NULL));// 随机数生成数据for (int i = 0; i < ST.table_len; i++) {// 生产的数字都在0-99中间ST.elem[i] = rand() % 100;}
}/** 打印顺序表*/
void st_print(SSTable ST) {for (int i = 0; i < ST.table_len; i++) {printf("%3d", ST.elem[i]);}printf("\n");
}/** 比较两个值的大小*/
int compare(const void *left, const void *right) {// 从大到小排序// return *(ElemType *)right - *(ElemType *)left;// 从小到大排序return *(ElemType *)left - *(ElemType *)right;
}/** 二分查找*/
int binary_search(SSTable L, ElemType key) {int low = 0, high = L.table_len, mid;while (low <= high) {mid = (low + high) / 2;if (L.elem[mid] == key) {// 找到了return mid;} else if (L.elem[mid] > key) {high = mid - 1;} else if (L.elem[mid] < key) {low = mid + 1;}}// 没有找到 不返回0是因为元素可能会在0号位置return -1;
}int main() {SSTable ST;// 一、顺序表初始化st_init(ST, 10);// 二、打印顺序表st_print(ST);// 三、排序qsort(ST.elem, ST.table_len, sizeof(ElemType), compare);st_print(ST);// 存储元素ElemType key;printf("please input search key:\n");scanf("%d", &key);// 元素存储位置int pos;pos = binary_search(ST, key);if (-1 != pos) {printf("find success, pos = %d\n", pos);} else {printf("find failed\n");}return 0;
}

这篇关于查找——顺序查找和折半查找的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1066596

相关文章

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中,location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求,NGINX 提供了多种匹

Verybot之OpenCV应用二:霍夫变换查找圆

其实我是想通过这个程序来测试一下,OpenCV在Verybot上跑得怎么样,霍夫变换的原理就不多说了,下面是程序: #include "cv.h"#include "highgui.h"#include "stdio.h"int main(int argc, char** argv){cvNamedWindow("vedio",0);CvCapture* capture;i

Win8下如何快速查找和删除电脑中的病毒

Win8系统如何查找和删除病毒?检查你的电脑是否存在病毒的一种快速方法是使用 Windows Defender. 此恶意软件防护随 Windows 提供,可帮助识别和删除病毒、间谍软件和其他恶意软件。   注意:如果你使用的是 Windows RT,则 Windows Defender 会始终启用,并且不能关闭。   如果你使用的是 Windows 8,则可以根据自己的喜好运行由其他

nyoj 685 查找字符串

当初一开始没做出来。 后来,学习过一段时间之后,在返回来做这道题,忽然发现,map类容器可以做。 PS:需要注意的是:此题如果用c++的输入输出的话,会超时。 O(time):gets()<  scanf() < cin。   附上代码: #include<stdio.h>#include<map>#include<string>#include<string.h>usin

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表,允许插入的一端叫做队尾(rear),允许删除的一端叫做队首(front)。 队列具有FIFO的性质 队列的存储表示也有两种方式:基于数组的,基于列表的。基于数组的叫做顺序队列,基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示:只提供了接口和显式的默认构造函数和析构函数,在派生类中调用。 #i

[数据结构]栈之顺序栈的类模板实现

栈的数组实现形式,采用动态分配数组,不够时可以调整栈的大小。 Stack.h文件:主要定义栈的抽象基类,提供公共的接口函数。 #ifndef STACK#define STACK//栈的抽象基类template<class T>class Stack{public:Stack(){}~Stack(){}virtual void Push(const T& x)=0;virt

【C++二分查找】2439. 最小化数组中的最大值

本文涉及的基础知识点 C++二分查找 LeetCode2439. 最小化数组中的最大值 给你一个下标从 0 开始的数组 nums ,它含有 n 个非负整数。 每一步操作中,你需要: 选择一个满足 1 <= i < n 的整数 i ,且 nums[i] > 0 。 将 nums[i] 减 1 。 将 nums[i - 1] 加 1 。 你可以对数组执行 任意 次上述操作,请你返回可以得到的 n

C++中类的构造函数调用顺序

当建立一个对象时,首先调用基类的构造函数,然后调用下一个派生类的 构造函数,依次类推,直至到达派生类次数最多的派生次数最多的类的构造函数为止。 简而言之,对象是由“底层向上”开始构造的。因为,构造函数一开始构造时,总是 要调用它的基类的构造函数,然后才开始执行其构造函数体,调用直接基类构造函数时, 如果无专门说明,就调用直接基类的默认构造函数。在对象析构时,其顺序正好相反。

七、Maven继承和聚合关系、及Maven的仓库及查找顺序

1.继承   2.聚合   3.Maven的仓库及查找顺序