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

飞书文档https://x509p6c8to.feishu.cn/wiki/LRdnwfhNgihKeXka7DfcGuRPnZt

顺序查找

查找算法是指：从一些数据之中，找到一个特殊的数据的实现方法。查找算法与遍历有极高的相似性，唯一的不同就是查找算法可能并不一定会将每一个数据都进行访问，有些查找算法如二分查找等，并不需要完全访问所有的数据。

查找算法适用于很多场景，最典型的应用场景就是已知次品商品的特征，如何从一堆商品当中查找出这些次品。

顺序查找算法是最简单的查找算法，其意思为：线性的从一个端点开始，将所有的数据依次访问，并求得所需要查找到的数据的位置，此时，线性查找可以称呼为遍历。

#include <stdio.h>

int sequential_search(int arr[], int n, int target) {
    int times = 0;
    for (int i = 0; i < n; i++) {
        times ++;
        printf("Find step : %d\n",times);
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 10, 11, 13, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 11;
    int index = sequential_search(arr, n, target);
    if (index == -1) {
        printf("Can not find %d in array.\n",target);
    } else {
        printf("Find %d in array.\n",target);
    }
    return 0;
}

二分查找

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

#include <stdio.h>

/**
1, 3, 5, 7, 9, 10, 11, 13, 15 -》10
low = 4 + 1 = 5
high = 8
10, 11, 13, 15-》10
10-》10
*/
int binarySearch(int arr[],int len,int target){
    int low,high;
    int mid;
    low = 0;
    high = len -1;
    int times = 0;
    while (1)
    {
        times ++;
        printf("当前正在进行第%d轮查找\n",times);
        mid = (high - low)/2 + low;
        if(target == arr[mid]){
            return mid;
        }else{
            if(target < arr[mid]){
                printf("需要查找的值可能在左边的区间\n");
                high = mid - 1;
            }else{
                printf("需要查找的值可能在右边的区间\n");
                low = mid + 1;
            }
        }
        if(low > high){
            return -1;
        }
    }
   

}

int main(){
    int arr[] = {1, 3, 5, 7, 9, 10, 11, 13, 15};
    int len = sizeof(arr)/sizeof(arr[0]);
    int target = 1;
    int status = binarySearch(arr,len,target);
    if(status == -1){
        printf("找不到需要查找的值\n");
    }else{
        printf("找到需要查找的值 位置是%d\n",status);
    }
}