【数据结构】顺序查找和二分查找

客官°小女子只卖身不卖艺 2024-04-17 05:31 172阅读 0赞

顺序查找，elem\[0\]作为哨兵位置，避免判断数组越界等敏感操作，Search\_Seq返回元素在顺序表中的位置

#include<iostream>
    using namespace std;
    const int MAX = 0xffff;
    typedef struct Table {
        int elem[MAX];
        int length;
    }Table;
    
    int Search_Seq(Table tb, int key) {
        tb.elem[0] = key;
        int i = 0;
        for (i = tb.length; tb.elem[i] != key; --i);
            return i;
    }
    
    void InitTable(Table &tb) {
        tb.length = 100;
        for (int i = 1; i <= tb.length; i++)
            tb.elem[i] = i*i;
    }
    int main() {
        Table tb;
        InitTable(tb);
        cout<<Search_Seq(tb, 81);
        return 0;
    }

二分查找，包括迭代版和递归版，函数返回元素在有序表中的位置

#include<iostream>
    #include<ctime>
    #include<algorithm>
    using namespace std;
    const int MAX = 0xffff;
    int elem[MAX];
    bool flag[MAX] = {false};
    
    void InitElem() {
        srand((int)time(0));
        for (int i = 0; i < MAX; i++)
            elem[i] = rand()%10000;
        sort(elem, elem + MAX);
    }
    
    // 非递归版
    int Binary_Search1(int key) {
        int low = 0, high = MAX - 1, mid;
        while (low <= high) {
            mid = (low + high) / 2;
            if (elem[mid] == key)
                return mid;
            else if (elem[mid] > key)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
    }
    
    // 递归版
    int Binary_Search2(int key, int low, int high) {
        int mid = (low + high) / 2;
        if (elem[mid] == key)
            return mid;
        else if (elem[mid] > key)
            return Binary_Search2(key, low, mid - 1);
        else
            return Binary_Search2(key, mid + 1, high);
        return -1;
    }
    
    int main()
    {
        InitElem();
        cout<<Binary_Search1(5000)<<endl;
        cout<<Binary_Search2(5000, 0, MAX - 1)<<endl;
        return 0;
    }