二分查找、分块查找、哈希查找

1.二分查找

---

二分查找就是折半查找，其基本思想是：首先选取表中间位置的记录，将其关键字与给定的关键字key进行比较， 若相等，则查找成功；若key值比该关键字值大，则要找的元素一定在右子表中，则继续对右子表进行折半查找； 若key值比该关键字值小，则要找的元素一定在左子表中，继续对左子表进行折半查找。如此地推，直到查找成功 或查找失败（查找范围为0）。 /*二分查找*/ /*本实例采用二分查找法查找特性关键字的元素。要求用户输入数组长度，也就是有序表的数据长度，并输入数据组元素和查找的关键字*/ #include<stdio.h> void binary_search(int key, int a[], int n) /*自定义函数binary_search*/ { int low, high, mid, count = 0, count1=0; low = 0; high = n - 1; while (low < high) /*当查找范围不为0时执行循环体语句*/ { count++; /*count记录查找次数*/ mid = (low + high) / 2; /*求取中间位置*/ if (key < a[mid]) /*key小于中间值时*/ high = mid - 1; /*确定左子表范围*/ else if (key>a[mid]) /*key大于中间值时*/ low = mid + 1; /*确定右子表范围*/ else if (key == a[mid]) /*当key等于中间值时，证明查找成功*/ { printf("查找成功！\n查找%d次！a[%d]%d", count, mid, key); /*输出查找次数及所查元素在数组中的位置*/ count1++; /*count1记录查找成功的次数*/ break; } } if (count1 == 0) /*判断是否查找失败*/ printf("查找失败！"); /*查找失败输出no found*/ } void main() { int key, a[100], n; printf("请输入数组的长度：\n"); scanf_s("%d", &n); printf("请输入数组元素：\n"); for (int i = 0; i < n; i++) scanf_s("%d", &a[i]); printf("请输入你想查找的元素：\n"); scanf_s("%d", &key); binary_search(key, a, n); printf("\n"); }

2.分块查找

---

分块查找也称为索引顺序查找，要求将待查找的元素均匀的分块，块间按大小排序，块内不排序， 所以要建立一个块的最大（或最小）关键字表，称为索引表。 本实例中给出的15个数按关键字大小分成了3块，这15个数的排列是一个有序序列，也可以给出 无序序列，**但必须满足分在第一块中的任意数都小于第二块中的所有数，第二块中的所有数都** **小于第三块中的所有数。**当要查找关键字key的元素时，先后顺序查找在已建好的索引表中查 找出key所在的块中，再在对应的块中顺序查找key，若key存在，则输出其相应的位置，否则输 出提示信息。 /*分块查找*/ /*采用分块查找在有序表中查找关键字*/ #include <stdio.h> struct index /*定义块的结构*/ { int key; /*块的关键字*/ int start; /*块的起始值*/ int end; /*块的结束值*/ }index_table[4]; /*定义结构体数组*/ int block_search(int key, int a[]) /*自定义实现分块查找*/ { int i, j; i = 1; while (i <= 3 && key > index_table[i].key) /*确定在哪个块中*/ i++; if (i > 3) /*大于分得的块数，则返回0*/ return 0; j = index_table[i].start; /*j等于块范围的起始值*/ while (j <= index_table[i].end&&a[j] != key)/*在确定的块内进行顺序查找*/ j++; if (j > index_table[i].end) /*如果大于块范围的结束值，则说明没有要查找的数，j置0*/ j = 0; return j; } void main() { int i, j = 0,k, key, a[16]; printf("请输入15个数：\n"); for (i = 1; i < 16; i++) scanf_s("%d", &a[i]); /*输入15个由小到大的数*/ for (i = 1; i <= 3; i++) { index_table[i].start = j + 1; /*确定每个块范围的起始值*/ j = j + 1; index_table[i].end = j + 4; /*确定每个块范围的结束值*/ j = j + 4; index_table[i].key = a[j]; /*确定每个块范围的最大值*/ } printf("请输入你想查找的元素：\n"); scanf_s("%d", &key); /*输入要查询的数值*/ k = block_search(key, a); /*调用函数进行查找*/ if (k != 0) printf("查找成功，其位置是：%d\n", k); /*如果找到该数，则输出提示信息*/ else printf("查找失败！"); /*若未找到，则输出提示信息*/ }

3.哈希查找

（进一步待完善）