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

查找

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

顺序查找

​ 顺序查找又称线性查找。它对于顺序表和链表都是适用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，则通过指针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;
}