C语言——搜索：查找某个数的位置（遍历，二分查找……）

在 C 语言编程里，搜索某个数在数组或者数据集合中的位置是一项基础且重要的操作。

一、遍历查找（顺序查找）

二、二分查找

三、插值查找

四、斐波那契查找

五、哈希查找

一、遍历查找（顺序查找）

（一）基本原理

遍历查找是最为基础的搜索方法，其核心思想是从数据集合的起始位置开始，逐个检查每个元素，直到找到目标元素或者遍历完整个数据集合。无论数据集合是否有序，都能使用该方法。

（二）代码示例


#include <stdio.h>// 遍历查找函数
/*
在sequentialSearch函数中，通过for循环逐个访问数组元素，将其与目标元素进行比较。
若相等，则返回该元素的索引；
若遍历完整个数组都未找到目标元素，则返回 -1。
*/
int sequentialSearch(int arr[], int n, int target) {for (int i = 0; i < n; i++) {if (arr[i] == target) {return i;}}return -1; // 未找到目标元素，返回 -1
}int main() {int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};int n = sizeof(arr) / sizeof(arr[0]);int target = 9;int result = sequentialSearch(arr, n, target);if (result != -1) {printf("目标元素 %d 的位置是 %d\n", target, result);} else {printf("未找到目标元素 %d\n", target);}return 0;
}

二、二分查找

（一）基本原理

二分查找要求数据集合必须有序（通常为升序）。其基本步骤是先找到数据集合的中间元素，将其与目标元素进行比较。若中间元素等于目标元素，则查找成功；若中间元素大于目标元素，则在左半部分继续查找；若中间元素小于目标元素，则在右半部分继续查找。不断重复这个过程，直至找到目标元素或者确定目标元素不存在。

（二）代码示例

#include <stdio.h>// 二分查找函数
/*
在binarySearch函数中，使用while循环不断缩小查找范围。
每次计算中间位置mid，并将中间元素与目标元素比较，根据比较结果更新查找范围的左右边界left和right。
*/int binarySearch(int arr[], int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1; // 未找到目标元素，返回 -1
}int main() {int arr[] = {1, 3, 4, 5, 6, 9, 10, 12, 15, 18};int n = sizeof(arr) / sizeof(arr[0]);int target = 10;int result = binarySearch(arr, 0, n - 1, target);if (result != -1) {printf("目标元素 %d 的位置是 %d\n", target, result);} else {printf("未找到目标元素 %d\n", target);}return 0;
}

三、插值查找

（一）基本原理

插值查找是对二分查找的改进，它基于数据集合是均匀分布的假设。通过插值公式计算中间位置，使得中间位置更接近目标元素，从而减少比较次数，提高查找效率。

（二）代码示例

#include <stdio.h>// 插值查找函数
/*
在interpolationSearch函数中，使用插值公式
pos = left + (((double)(target - arr[left]) / (arr[right] - arr[left])) * (right - left))
计算中间位置pos，然后根据中间元素与目标元素的比较结果更新查找范围。
*/int interpolationSearch(int arr[], int left, int right, int target) {while (left <= right && target >= arr[left] && target <= arr[right]) {if (left == right) {if (arr[left] == target) return left;return -1;}// 插值公式计算中间位置int pos = left + (((double)(target - arr[left]) / (arr[right] - arr[left])) * (right - left));if (arr[pos] == target) {return pos;} else if (arr[pos] < target) {left = pos + 1;} else {right = pos - 1;}}return -1; // 未找到目标元素，返回 -1
}int main() {int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};int n = sizeof(arr) / sizeof(arr[0]);int target = 18;int result = interpolationSearch(arr, 0, n - 1, target);if (result != -1) {printf("目标元素 %d 的位置是 %d\n", target, result);} else {printf("未找到目标元素 %d\n", target);}return 0;
}

四、斐波那契查找

（一）基本原理

斐波那契查找也是对二分查找的一种改进，它利用斐波那契数列来分割数据集合。该方法适用于数据集合规模较大且存储在磁盘等外部设备上的情况。

（二）代码示例

#include <stdio.h>// 获取斐波那契数列的第 n 项
/*
getFibonacci函数用于生成斐波那契数列的第n项。
fibonacciSearch函数先找到大于或等于数组长度n的最小斐波那契数，
然后根据斐波那契数列的性质分割数据集合，
逐步缩小查找范围。
*/int getFibonacci(int n) {if (n == 0) return 0;if (n == 1) return 1;return getFibonacci(n - 1) + getFibonacci(n - 2);
}// 斐波那契查找函数
int fibonacciSearch(int arr[], int n, int target) {int fib2 = 0; // (m-2)'th Fibonacci No.int fib1 = 1; // (m-1)'th Fibonacci No.int fibM = fib2 + fib1; // m'th Fibonacci// 找到大于或等于 n 的最小斐波那契数while (fibM < n) {fib2 = fib1;fib1 = fibM;fibM = fib2 + fib1;}int offset = -1;// 开始查找while (fibM > 1) {int i = (offset + fib2 < n)? (offset + fib2) : (n - 1);if (arr[i] < target) {fibM = fib1;fib1 = fib2;fib2 = fibM - fib1;offset = i;} else if (arr[i] > target) {fibM = fib2;fib1 = fib1 - fib2;fib2 = fibM - fib1;} else {return i;}}if (fib1 && arr[offset + 1] == target) {return offset + 1;}return -1; // 未找到目标元素，返回 -1
}int main() {int arr[] = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};int n = sizeof(arr) / sizeof(arr[0]);int target = 85;int result = fibonacciSearch(arr, n, target);if (result != -1) {printf("目标元素 %d 的位置是 %d\n", target, result);} else {printf("未找到目标元素 %d\n", target);}return 0;
}

五、哈希查找

（一）基本原理

哈希查找通过哈希函数将目标元素映射到哈希表的某个位置，然后直接访问该位置来查找目标元素。哈希函数的设计至关重要，好的哈希函数可以减少哈希冲突，提高查找效率。

（二）代码示例

#include <stdio.h>
#include <stdlib.h>#define TABLE_SIZE 10/*
hashFunction是一个简单的哈希函数，
将键值对key映射到哈希表的索引位置。
hashSearch函数通过哈希函数计算目标元素的索引，
然后检查该位置是否存储着目标元素。
*/// 简单的哈希函数
int hashFunction(int key) {return key % TABLE_SIZE;
}// 哈希查找函数
int hashSearch(int hashTable[], int key) {int index = hashFunction(key);if (hashTable[index] == key) {return index;}return -1; // 未找到目标元素，返回 -1
}int main() {int hashTable[TABLE_SIZE] = {0};int keys[] = {12, 25, 35, 47};for (int i = 0; i < sizeof(keys) / sizeof(keys[0]); i++) {int index = hashFunction(keys[i]);hashTable[index] = keys[i];}int target = 35;int result = hashSearch(hashTable, target);if (result != -1) {printf("目标元素 %d 的位置是 %d\n", target, result);} else {printf("未找到目标元素 %d\n", target);}return 0;
}