算法-查找

学习并记录下查找算法，方便回顾。

查找算法 | 平均时间复杂度 | 空间复杂度 | 查找条件 ---|---|---|+++ 顺序查找 | O(n) | O(1) | 无序 二分查找（折半查找）| O(log₂n)| O(1) | 有序 分块查找（索引顺序查找）| | | 插值查找 | O(log₂(log₂n)) | O(1) | 有序 斐波那契查找 | O(log₂n) | O(1) | 有序 哈希查找| O(1) | O(n) | 无序 二叉查找树（二叉搜索树查找） |O(log₂n) | | 红黑树|O(log₂n) | | 2-3树 | O(log₂n - log₃n) | | B树/B+树 |O(log₂n) | |

顺序查找

顺序查找适合于存储结构为顺序存储或链接存储的线性表，属于无序查找算法。

int SeqSearch(vector<int> &v, int val){
    for(int i = 0; i < v.size(); ++i){
        if(v[i] == val)return i;
    }
    return -1;
}

二分查找

元素必须是有序的，如果是无序的则要先进行排序操作，属于有序查找算法。

//迭代方式
int BinarySearch(vector<int> &v, int val, int low, int high){
    if(v.size() <= 0)return -1;
    
    while(low <= high){
        int mid = low + (high - low)/2;
        if(v[mid] == val)return mid;
        else if(v[mid] > val)high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

//递归方式
int BinarySearch(vector<int> &v, int val, int low, int high){
    if(v.size() <= 0)return -1;
    if(low > high)
        return -1;
    int mid = low + (high - low)/2;
    if(v[mid] == val)
        return mid;
    else if(v[mid] > val)
        return BinarySearch(v, val, low, mid - 1);
	else
        return BinarySearch(v, val, mid + 1, high);
}

分块查找

插值查找

基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率，属于有序查找。

二分查找：$mid = low + {1 \over 2}(high - low) $

插值查找：$mid = low + {val - v[low] \over v[high] - v[low]}(high - low) $

//迭代方式
int InsertSearch(vector<int> &v, int val, int low, int high){
    if(v.size() <= 0)return -1;
    
    while(low <= high){
        int mid = low + (val - v[low])/(v[high] - v[low]) *  (high - low);
        if(v[mid] == val)return mid;
        else if(v[mid] > val)high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

//递归方式
int InsertSearch(vector<int> &v, int val, int low, int high){
    if(v.size() <= 0)return -1;
    if(low > high)return -1;
    
    int mid = low + (val - v[low])/(v[high] - v[low]) *  (high - low);
    if(v[mid] == val)
        return mid;
    else if(v[mid] > val)
        return InsertSearch(v, val, low, mid - 1);
	else
        return InsertSearch(v, val, mid + 1, high);
}

斐波那契查找

基于二分查找算法，通过运用黄金比例的概念选择点进行查找，提高查找效率，属于有序查找算法。

随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，将黄金比例运用到查找技术中。

要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1

int f[20];

void Fibonacci(){
    f[0] = 0;
    f[1] = 1;
    for(int i = 2; i < 20; ++i)
        f[i] = f[i-1] + f[i-2];
}

int FibonacciSearch(vector<int> &v, int n, int val){
    int low = 0;
    int high = n - 1;
    
    int k = 0;
    while(n > f[k] - 1)++k;
    
    vector<int> temp(v);
    for(int i = n; i < f[k] - 1; ++i)
        temp.push_back(v[n-1]);
    
    while(low <= high){
        int mid = low + f[k-1] - 1;
        if(val < temp[mid]){
            high = mid - 1;
            k -= 1;
        }
        else if(val > temp[mid]){
            low = mid + 1;
            k -= 2;
        }
        else{	//判断是否扩展的数值
            if(mid < n)return mid;
            else return n - 1;
        }
    }
    return -1;
}

二叉树查找

在二叉搜索树b中查找x的过程为：

• 若b是空树，则搜索失败，否则：
• 若x等于b的根节点的数据域之值，则查找成功；否则：
• 若x小于b的根节点的数据域之值，则搜索左子树；否则：
• 查找右子树

BSTNode *BSTSearch(BSTNode *node, int val){
    while(node != NULL){
        if(val < node -> val)node = node -> left;
        else if(val > node -> val)node = node -> right;
        else return node;
    }
    return nullptr;
}