几种查找方法

喜欢ヅ旅行 2022-05-26 00:37 255阅读 0赞

#### 前言 ####

在一个数组中，对于数据的查找方法有多种，下面介绍几种最常见的元素查找

#### 1、普通查找 ####

这是最简单粗暴的查找方式，通过遍历所有元素，找到最数组中的位置。通过代码简单实现

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define MAX 10
    
    int searchNum(int a[], int data) {
        int pos = -1;
        for(int i=0; i < MAX; i++) {
            if(a[i] == data) {
                pos = i;
                break;
            }
        }
        return pos;
    }
    int main() {
        int a[MAX];
        for(int i=0; i < MAX; i++) {
            int t = rand() % 10;
            a[i] = t;
        }
        int pos = searchNum(&a, 4);
        if(pos == -1) printf("NOT FOUND");
        else printf("the position is: %d ", pos);
        return 0;
    }

#### 2、普通查找（哨兵） ####

我们这一次查找也是普通查找，只是我们通过采用哨兵的形式，能够使代码更加简洁。主要原理就是我们在数组的第一个a\[0\]放我们需要查找的元素，然后从最后一个开始向前遍历，如果发现有一个和查找元素相等，那么就说明我们已经找到了，如果一直没有发现，那么遍历的时候在遍历到a\[0\]的时候仍然会相等。因此我们最后的位置是0，那么就是没有找到，否则就是找到了

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define MAX 10
    
    int searchNum(int a[], int data) {
        int pos;
        for(pos=MAX; a[pos] != data; pos--);
        return pos;
    }
    int main() {
        int a[MAX];
        int data = 4;
        a[0] = data;
        for(int i=1; i < MAX; i++) {
            int t = rand() % 10;
            a[i] = t;
        }
        int pos = searchNum(&a, data);
        if(pos == 0) printf("NOT FOUND");
        else printf("the position is: %d ", pos);
        return 0;
    }

#### 3、二分查找 ####

这是最经典的查找方式，通过此种方法进行查找，需要满足两个条件，第一数据是按照顺序排列的，第二是数据必须放在数组中的。在一组有序数据中，我们先找到中间的数据，判断我们需要查找的数据和数组中间数据的大小，如果中间的数据大于我们需要查找的数据，那么就在数组前半部分进行查找，如果小于需要查找的数据，那么就在后半部分查找。

#include<stdio.h>
    #include<stdlib.h>
    #include<math.h>
    #define MAX 10
    
    int searchNum(int a[], int data) {
        int left = 0, right = MAX - 1;
        int middle = (left + right) / 2;
        int flag = 0;
        while(left <= right) {
            if(a[middle] < data) left = middle + 1;
            else if(a[middle] > data) right = middle - 1;
            else { flag = 1; break; }
            middle = (left + right) / 2;
        }
        if(flag) return middle;
        return -1;
    }
    int main() {
        int a[MAX];
        memset(a, 0, sizeof(a));
        int data = 10;
        for(int i=1; i < MAX; i++) {
            int t = rand() % 10 + 1;
            a[i] = t + a[i-1];
        }
        int pos = searchNum(&a, data);
        if(pos == -1) printf("NOT FOUND");
        else printf("the position is: %d ", pos);
        return 0;
    }