七大查找常见算法（上）

139 阅读 0 评论 92 点赞

我是靠谱客的博主现代小懒猪，最近开发中收集的这篇文章主要介绍七大查找常见算法（上），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、顺序查找算法
1.1 基本思想
顺序查找是在一个已知无(或有序）序队列中找出与给定关键字相同的数的具体位置。原理是让关键字与队列中的数从最后一个开始逐个比较，直到找出与给定关键字相同的数为止，它的缺点是效率低下。
1.2 实现代码
（1） C++实现：

//顺序查找
int Sequence_Search(int a[], int value, int n)
{
    int i;
    for(i=0; i<n; i++)
        if(a[i]==value)
            return i;
    return -1;
}

（2）python实现：

def Sequence_Search(nums, target):   
     if len(nums)==0:
            return False
     for i in range(len(nums)):     
        if nums[i]==target:          
            return True
     return False

1.3 时间复杂度分析
查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2；当查找不成功时，需要n+1次比较，时间复杂度为O(n)；所以，顺序查找的时间复杂度为O(n)。

二、折半查找
2.1 基本思想
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
1.1.2 实现代码
（1） C++实现：

//二分查找，递归版本
int BinarySearch2(int a[], int value, int low, int high)
{
    int mid = low+(high-low)/2;
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return BinarySearch2(a, value, low, mid-1);
    if(a[mid]<value)
        return BinarySearch2(a, value, mid+1, high);
}

//二分查找（折半查找），非递归版本
int BinarySearch1(int a[], int value, int n)
{
    int low, high, mid;
    low = 0;
    high = n-1;
    while(low<=high)
    {
        mid = (low+high)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            high = mid-1;
        if(a[mid]<value)
            low = mid+1;
    }
    return -1;
}

（2） python版本

#-----------------递归二分查找------------------
def binary_Search(nums,target,left,right):
    if len(nums)==0:
        return False
    mid=(left+right)//2
    while left<=right:
        if nums[mid]>target:
            return binary_Search(nums, target, left, mid-1)
        elif nums[mid]<target:
            return binary_Search(nums, target, mid+1, right)
        else:
            return mid

if __name__ == '__main__':
    list = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    low=0
    high=len(list)-1
    result = binary_Search(list,444,low,high)
    print(result)
#-------------------非递归查找------------------------
def binary_Search(nums,target):
    if len(nums)==0:
        return False
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = (low+high)//2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False

if __name__ == '__main__':
    list = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = binary_Search(list,444)
    print(result)

2.3 时间复杂度分析
最坏情况下，关键词比较次数为⌊log₂n⌋+1，最好情况就是1，所以二分查找的时间复杂度为O(logn)。它显然好于顺序查找的O(n)。

三、插值查找
3.1 基本思想
在讲基本思想之前，我们一个问题，如果在1~50000的数中查找数字5，按照正常的思维应该是从下标为0的地方开始查找，这就是经验，我们此时不会再从中点（25000）进行查找，这样效率太低，查找速度太慢。所以我们可以考虑用一种自适应的方法来实现查找，提高查找效率，改进二分查找效率。
在二分查找中查找点计算如下：
mid=(low+high)/2, 即mid=low+1/2*(high-low);
通过类比，我们可以将查找的点改进为如下：
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，
所以差值查找的核心思想就是基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。
3.2 实现代码
（1） C++实现：

//插值查找
int InsertionSearch(int a[], int value, int low, int high)
{
    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return InsertionSearch(a, value, low, mid-1);
    if(a[mid]<value)
        return InsertionSearch(a, value, mid+1, high);
}

（2）python代码

# 插值查找算法
# 时间复杂度O(log(n))
def insert_search(lis, key):
    low = 0
    high = len(lis) - 1
    time = 0
    while low < high:
        time += 1
        # 计算mid值是插值算法的核心代码
        mid = low + int((high - low) * (key - lis[low])/(lis[high] - lis[low]))
        print("mid=%s, low=%s, high=%s" % (mid, low, high))
        if key < lis[mid]:
            high = mid - 1
        elif key > lis[mid]:
            low = mid + 1
        else:
            # 打印查找的次数
            print("times: %s" % time)
            return mid
    print("times: %s" % time)
    return False

if __name__ == '__main__':
    LIST = [1, 5, 7, 8, 22, 54, 99, 123, 200, 222, 444]
    result = insert_search(LIST, 444)
    print(result)

3.3 时间复杂度分析
它的时间复杂度跟二分查找的时间复杂度一样，为O(logn)。需要注意的是对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。

四、斐波那契查找
4.1 基本思想
斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

它也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。
斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，即n=F(k)-1；开始将key值（要查找的数据）与第F(k-1)位置的记录进行比较(即mid=low+F(k-1)-1)，比较结果也分为三种：
（1）相等，mid位置的元素即为所求；
（2）大于，low=mid+1，k-=2。说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。
（3）小于，high=mid-1，k-=1。说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找。
4.2 实现代码
（1）C++实现

// 斐波那契查找
#include "stdafx.h"
#include <memory>
#include  <iostream>
using namespace std;

const int max_size=20;//斐波那契数组的长度
/*构造一个斐波那契数组*/ 
void Fibonacci(int * F)
{
    F[0]=0;
    F[1]=1;
    for(int i=2;i<max_size;++i)
        F[i]=F[i-1]+F[i-2];
}
/*定义斐波那契查找法*/  
int FibonacciSearch(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
{
  int low=0;
  int high=n-1;

  int F[max_size];
  Fibonacci(F);//构造一个斐波那契数组F 
  int k=0;
  while(n>F[k]-1)//计算n位于斐波那契数列的位置
      ++k;
  int  * temp;//将数组a扩展到F[k]-1的长度
  temp=new int [F[k]-1];
  memcpy(temp,a,n*sizeof(int));

  for(int i=n;i<F[k]-1;++i)
     temp[i]=a[n-1];

  while(low<=high)
  {
    int mid=low+F[k-1]-1;
    if(key<temp[mid])
    {
      high=mid-1;
      k-=1;
    }
    else if(key>temp[mid])
    {
     low=mid+1;
     k-=2;
    }
    else
    {
       if(mid<n)
           return mid; //若相等则说明mid即为查找到的位置
       else
           return n-1; //若mid>=n则说明是扩展的数值,返回n-1
    }
  }  
  delete [] temp;
  return -1;
}

int main()
{
    int a[] = {0,16,24,35,47,59,62,73,88,99};
    int key=100;
    int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
    cout<<key<<" is located at:"<<index;
    return 0;
}

（2）python实现

import random
#source为待查找数组，key为要查找的数
def fibonacciSearch(source,key):
    #生成裴波那契数列
    fib = [0,1]
    for i in range(1,36):
        fib.append(fib[-1]+fib[-2])

    #确定待查找数组在裴波那契数列的位置
    k = 0
    n = len(source)

    #此处 n>fib[k]-1 也是别有深意的
    #若n恰好是裴波那契数列上某一项，且要查找的元素正好在最后一位，此时必须将数组长度填充到数列下一项的数字
    while(n > fib[k]-1):
        k = k + 1
    #将待查找数组填充到指定的长度
    for i in range(n,fib[k]):
        a.append(a[-1])
    low,high = 0,n-1
    while(low <= high):
        #获取黄金分割位置元素下标
        mid = low + fib[k-1] - 1 
        if(key < a[mid]):
            #若key比这个元素小,则key值应该在low至mid-1之间，剩下的范围个数为F(k-1)-1
            high = mid - 1
            k = k -1
        elif(key > a[mid]):
            #若key比这个元素大,则key至应该在mid+1至high之间，剩下的元素个数为F(k)-F(k-1)-1=F(k-2)-1
            low = mid + 1
            k = k - 2
        else:
            if(mid < n):
                return mid
            else:
                return n-1
    return -1

### 函数测试 ###
#生成待查找的数组
a = [random.randint(1,100000) for x in range(0,33)]
a.append(673990)
a.sort()
#待查找的数
key = 673990
#输出查找到的位置下标
print(fibonacciSearch(a,key))

4.3 时间复杂度分析
斐波那契查找的整体时间复杂度也为O(log(n))。但就平均性能，要优于二分查找。但是在最坏情况下，比如这里如果key为1，则始终处于左侧半区查找，此时其效率要低于二分查找。
4.4 总结
二分查找的mid运算是加法与除法，插值查找则是复杂的四则运算，而斐波那契查找只是最简单的加减运算。在海量数据的查找中，这种细微的差别可能会影响最终的查找效率。因此，三种有序表的查找方法本质上是分割点的选择不同，各有优劣，应根据实际情况进行选择。