进阶-数据结构部门：3、常用查找算法

飞书文档

https://x509p6c8to.feishu.cn/wiki/LRdnwfhNgihKeXka7DfcGuRPnZt
次序查找

查找算法是指：从一些数据之中，找到一个特别的数据的实现方法。查找算法与遍历有极高的相似性，唯一的差别就是查找算法大概并不肯定会将每一个数据都举行访问，有些查找算法如二分查找等，并不必要完全访问所有的数据。
查找算法适用于很多场景，最典型的应用场景就是已知次品商品的特性，如何从一堆商品当中查找出这些次品。
次序查找算法是最简单的查找算法，其意思为：线性的从一个端点开始，将所有的数据依次访问，并求得所必要查找到的数据的位置，此时，线性查找可以称谓为遍历。

2. #include <stdio.h>
4. int sequential_search(int arr[], int n, int target) {
5.     int times = 0;
6.     for (int i = 0; i < n; i++) {
7.         times ++;
8.         printf("Find step : %d\n",times);
9.         if (arr[i] == target) {
10.             return i;
11.         }
12.     }
13.     return -1;
14. }
16. int main() {
17.     int arr[] = {1, 3, 5, 7, 9, 10, 11, 13, 15};
18.     int n = sizeof(arr) / sizeof(arr[0]);
19.     int target = 11;
20.     int index = sequential_search(arr, n, target);
21.     if (index == -1) {
22.         printf("Can not find %d in array.\n",target);
23.     } else {
24.         printf("Find %d in array.\n",target);
25.     }
26.     return 0;
27. }

复制代码

二分查找

二分查找也称折半查找（Binary Search），多数的人喜欢叫他二分查找。它是一种服从较高的查找方法。但是，折半查找要求线性表必须采用次序存储结构，而且表中元素按关键字有序分列，注意必须要是有序分列。

2. #include <stdio.h>
4. /**
5. 1, 3, 5, 7, 9, 10, 11, 13, 15 -》10
6. low = 4 + 1 = 5
7. high = 8
8. 10, 11, 13, 15-》10
9. 10-》10
10. */
11. int binarySearch(int arr[],int len,int target){
12.     int low,high;
13.     int mid;
14.     low = 0;
15.     high = len -1;
16.     int times = 0;
17.     while (1)
18.     {
19.         times ++;
20.         printf("当前正在进行第%d轮查找\n",times);
21.         mid = (high - low)/2 + low;
22.         if(target == arr[mid]){
23.             return mid;
24.         }else{
25.             if(target < arr[mid]){
26.                 printf("需要查找的值可能在左边的区间\n");
27.                 high = mid - 1;
28.             }else{
29.                 printf("需要查找的值可能在右边的区间\n");
30.                 low = mid + 1;
31.             }
32.         }
33.         if(low > high){
34.             return -1;
35.         }
36.     }
37.    
39. }
41. int main(){
42.     int arr[] = {1, 3, 5, 7, 9, 10, 11, 13, 15};
43.     int len = sizeof(arr)/sizeof(arr[0]);
44.     int target = 1;
45.     int status = binarySearch(arr,len,target);
46.     if(status == -1){
47.         printf("找不到需要查找的值\n");
48.     }else{
49.         printf("找到需要查找的值 位置是%d\n",status);
50.     }
51. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。