精华内容
下载资源
问答
  • 三种有序表的查找算法

    千次阅读 2019-08-26 11:52:06
    三种有序表查找及其心得体会有序查找算法简介排序算法种类二分查找算法时间复杂度插值查找算法时间复杂度斐波那契查找算法时间复杂度总结参考文献 有序查找算法简介 查找的是一个有序线性表,并进行查找操作的...

    有序表查找算法简介

    查找的是一个有序线性表,并进行查找操作的查找表

    排序算法种类

    按照算法复杂程度分类
    这里主要以二分查找,插值查找,斐波那契查找为例子

    二分查找

    折半查找(Binary Search)技术,又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。折半查找的基本思想是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。

    • 中心思想:有序取中,比较左右,折半查找。

    在这里插入图片描述

    算法

    1  int Binary_Search(int *a,int n,int key)
    2  {
    3      int low,high,mid;
    4      int low=1;
    5      int high=n;
    6      while(low<=high)
    7     {
    8          mid=(low+high)/2; 
    9          if(key<a[mid])
    10            high=mid-1; 
    11         else if (key>a[mid])
    12            1ow=mid+1; 
    13         else 
    14            return mid;
    15    }
    16 }
    

    时间复杂度

    具有n个结点的完全二又树的深度为 ⌊ log ⁡ 2 n ⌋ + 1 \lfloor \log _2n \rfloor +1 log2n+1。在这里尽管折半查找判定二叉树并不是完全二叉树,但同样相同的推导可以得出,最坏情况是查找到关键字或查找失败的次数为 ⌊ log ⁡ 2 n ⌋ + 1 \lfloor \log _2n \rfloor +1 log2n+1

    插值查找

    插值查找(Interpolation Search)是根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式 k e y − a [ l o w ] a [ h i g h ] − a [ l o w ] \frac{key-a\left[ low \right]}{a\left[ high \right] -a\left[ low \right]} a[high]a[low]keya[low]

    • 中心思想:插值公式

    在这里插入图片描述
    在这里插入图片描述

    算法

    1  int Interpolation_Search(int *a,int n,int key)
    2  {
    3      int low,high,mid;
    4      int low=1;
    5      int high=n;
    6      while(low<=high)
    7     {
    8          mid=low+(high-1ow)*(key-a[low])/(a[highl-a[low]);/*插值改动处*/
    9          if(key<a[mid])
    10            high=mid-1; 
    11         else if (key>a[mid])
    12            1ow=mid+1; 
    13         else 
    14            return mid;
    15    }
    16 }
    

    时间复杂度

    时间复杂度:O(logn)

    斐波那契查找

    斐波那契查找(Fibonaci Search),它是利用了黄金分割原理来实现的。

    • 中心思想:将线性表都成斐波那契数列,然后后黄金分割取上下限

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    算法

    1  int Fibonacci_Search(int *a,int n,int key)
    2  {
    3       int low,high,mid,i,k;
    4   	low=1;
    5	    high=n;
    6   	k=0;
    7   	while(n>F[k]-1)
    8   	   k++;
    9   	for(i=n;i<=f[k]-1;i++)
    10   	   a[i]=a[n];
    11   	while(low<=high)
    12   	{
    13   		mid=low+f[k-1]-1;
    14   		if(key<a[mid])
    15   		{
    16   			high=mid-1;
    17   			k=k-1;
    18   		}
    19   		else if(key>a[mid])
    20   		{
    21   			low=mid+1;
    22   			k=k-2;
    23   		}
    24   		else
    25   		{
    26   			if(mid<=n)
    27   			   return mid;
    28   			else 
    29  			   return n;
    30   		}
    31   	}
    32   	return 0;
    33   } 
    

    时间复杂度

    尽管斐波那契查找的时间复杂也O(logn),但就平均性能来说,斐波那契查找要优于折半查找。可惜如果是最坏情况,比如这里key=1,那么始终都处于左侧长半区在查找,则查找效率要低于折半查找。

    总结

    1. 应该说,三种有序表的查找本质上是分隔点的选择不同,各有优劣,实际开发时可根据数据的特点综合考虑再做出选择。
    2. 未知的数据首先考虑二分查找
    3. 均匀的数据适合插值查找
    4. 如果要查找的记录在右侧,则左侧的数据都不用再判断了,不断反复进行下去,对处于当中的大部分数据,斐波那契查找工作效率要高一些。

    参考文献

    [[1]] 程杰. 大话数据结构[M]. 清华大学出版社, 2011.
    [[2]] 啊哈磊. 啊哈! 算法[M]. 人民邮电出版社, 2014.

    展开全文
  • 主要介绍了PHP有序表查找之插值查找算法,简单分析了插值查找算法的概念、原理并结合实例形式分析了php实现针对有序表插值查找的相关操作技巧,需要的朋友可以参考下
  • 静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法 静态查找表。实现有序表的折半查找算法静态查找表。实现有序表的折半查找算法
  • 主要介绍了Python有序查找算法之二分法,结合实例形式分析了Python二分查找算法的原理与相关实现技巧,需要的朋友可以参考下
  • 主要介绍了Python查找两个有序列表中位数的方法,结合实例形式分析了Python基于归并算法遍历、计算有序列表相关操作技巧,需要的朋友可以参考下
  • 主要介绍了PHP有序表查找之二分查找(折半查找)算法,简单介绍了二分查找法的概念、原理并结合实例形式分析了php基于二分查找算法进行有序线性表查找的相关操作技巧,需要的朋友可以参考下
  • 这篇文章主要介绍了python有序查找算法 二分法实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 二分法是一种快速查找的方法,时间复杂度低,逻辑简单...
  • 静态查找表:只进行查找操作的查找表 动态查找表:在查找过程中同时插入查找表中不存在的元素,或者删除已存在的元素 本文主要总结静态查找表 1.顺序表查找:从第一个或者最后一个记录开始,将每个记录的关键字与...

    静态查找表只进行查找操作的查找表

    动态查找表:在查找过程中同时插入查找表中不存在的元素,或者删除已存在的元素


    本文主要总结静态查找表

    1.顺序表查找:从第一个或者最后一个记录开始,将每个记录的关键字与给定值比较,若相等则查找成功。

    C++实现:

    for(int i=0;i<n;i++)

    {

        if(a[i]==key)

            return i;

    }

    return 0;


    时间复杂度:

    最好情况:O(1),第一次就找到

    最坏情况:O(n),需要逐个比较完

    平均:O(n)


    2.有序表查找:元素是有序排列的,且是顺序存储的(存在数组或者vector)。主要包括二分查找,插值查找,斐波拉契查找


    2.1二分查找(折半查找)

    基本思想:

    (1)与中间元素比较,其中mid=low+1/2*(low+high)

    (2)等于中间元素,则查找成功

    (3)大于中间元素,在它的右半区查找,重复(1);小于中间元素,在它的左半区查找,重复(1),直到找到给定值。

    C++实现:

    //n是有序表长度

    int low=0,high=n-1;

    while(low<high)

    {

        int mid=(low+high)/2;

        if(key<a[mid])

            high=mid-1;

        else if(key>a[mid])

            low=mid+1;

        else

            return mid;     

    }

    return 0;

    时间复杂度:

    最好:O(1)

    最坏:O(logn+1)

    平均:O(logn)


    2.2插值查找(折半查找升级版)

    二分查找中:

    mid=low+1/2*(low+high)

    插值查找:

    mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low),也就是将上述的比例参数1/2改进了,根据关键字在整个有序表中所处的位置,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数

    因为如果在一个有序表中找相对较小的元素(即离low更近一点),就mid向low靠近一点;找相对较大的元素(即离high更近一点),就mid向high靠近一点;这样效率比较高。但要求表中元素分布比较均匀。

    时间复杂度:O(logn)


    2.3斐波那契查找

    斐波拉契数列:0,1,1,2,3,5,8,13,21,34,F(k)

    基本思想:

    (1)将有序数组的数值补全,使它的长度等于某个斐波拉契数F(k)-1

    (2)取low=0,mid=low+F(k-1)-1,high=F(k)-2

    (3)当给定值小于a[mid]值,在mid前半段查找,且前半段长度为F(k-1)-1;当给定值大于a[mid]值,在mid后半段查找,且后半段长度为F(k-2)-1;重复(2)

    时间复杂度:O(logn)

    因为斐波拉契查找求mid=low+F(k-1)-1,只有加减法,没有乘法,这种细微差别相比较前两种方法要好一些。

    C++实现:

    int low=0,high=n-1,mid,k=0;

    while(n>F(k)) 

        k++;

    for(i=n;i<F(k)-2;i++)

        a[i]=a[n-1];

    while(low<high)

    {

        mid=low+F(k-1)-1;

        if(key<a[mid])

        {

            high=mid-1;

            k=k-1;

        }

        else if(key>a[mid])

        {

            high=mid+1;

            k=k-2;

        }

        else

        {

            if(mid<=n) return mid;

            else return n;  //是后面补的

    }

    return 0;


    3.散列表查找(哈希表,hash table)

    散列表:关键字key和存储位置之间有一个确定关系f,称为散列函数(哈希函数),要找到关键字key,只需计算f(key)就可以直接得到存储位置。连续存储。查找复杂度O(1)。

    但有时候两个不同的关键字k1和k2,f(k1)=f(k2),会产生冲突。这就尴尬了……所以尽量构造散列函数让冲突尽可能少。

        

    展开全文
  • 1. 顺序查找,时间复杂度为O(n) 2. 二分查找,时间复杂度...a) 二叉树查找算法,插入和查找的时间复杂度均为O(logn) b) 红黑树,logn c) B树和B+树,O(log n) 6. 分块查找,关键字构成一个索引表 7. 哈希查找,...

    1.     顺序查找,时间复杂度为O(n)

    2.     二分查找,时间复杂度为O(log2n)

    3.     插值查找,关键字分布又比较均匀, 时间复杂度为O(log2(log2n))

    4.     斐波那契查找,时间复杂度为O(log2n)

    5.     树表查找

    a)     二叉树查找算法,插入和查找的时间复杂度均为O(logn)

    b)     红黑树,logn

    c)     B树和B+树,O(log n)

    6.     分块查找,关键字构成一个索引表

    7.      哈希查找,以空间换时间的算法

    折半查找,每次都是1/2,设寻找t次,等式为2t =n,n为数据的总数

    展开全文
  •  二分查找也称为是折半查找,属于有序查找算法。元素必须是有序的,如果是无序的则要先进行排序操作。二分查找的前提条件是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,二分查找能得到不错的效率。但...

    二分查找

          二分查找也称为是折半查找,属于有序查找算法。元素必须是有序的,如果是无序的则要先进行排序操作。二分查找的前提条件是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,二分查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说,维护有序的排序会带来不小的工作量,那就不建议使用。

    原理:

           二分查找用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。

    算法详细描述:

    • 选择一个可以将列表arr大致一份为二的索引i;
    • 检查是否有arr[i] == target;
    • 如果不是,检查arr[i]大于还是小于target;
    • 根据上一步的结果,确定在arr的左半部分还是右半部分搜索target。

    代码实现:

    ## 递归版本
    def binarySearch(arr, target):
        """
        假设arr是列表,其中元素按升序排列.
        如果target是arr中的元素,则返回True,否则返回False
        """
    
        def bSearch(arr, target, low, high):
            if high == low:
                return arr[low] == target
            mid = (low + high) // 2
            if arr[mid] == target:
                return True
            elif arr[mid] > target:
                if low == mid:
                    return False
                else:
                    return bSearch(arr, target, low, mid - 1)
            else:
                return bSearch(arr, target, mid + 1, high)
    
        if len(arr) == 0:
            return False
        else:
            return bSearch(arr, target, 0, len(arr) - 1)
    
    ## 非递归版本
    def binarySearch(arr, target):
        low = 0
        high = len(arr) - 1
        while low < high:
            mid = (low + high) // 2
            if target < arr[mid]:
                high = mid - 1
            elif target > arr[mid]:
                low = mid + 1
            else:
                return True
        return False
    

    时间复杂度:

           假设,总共有n个元素,每次查找的区间大小就是n,n/2,n/4,…,n/2^k(接下来操作元素的剩余个数),其中k就是循环的次数。由于n/2^k取整后>=1,即令n/2^k=1,可得k=log2n,(是以2为底,n的对数),所以时间复杂度可以表示O()=O(logn)

     

    展开全文
  • 有序表查找---折半查找算法

    万次阅读 2019-03-10 20:00:31
    折半查找的基本思想是:在有序表中,取中间值为比较对象,如果给定的值和中间值的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定的值大于中间值的关键字,则在中间...
  • 有序查找算法总结

    千次阅读 2018-01-17 20:22:31
    有序表:按一定顺序排列的表。  1、折半查找:又称二分查找,直接上代码、 public int BinarySerch(int[] a,key){ int low=1,high=a.length,mid; while( low ){ mid = low + (high - low) / 2; if( key [mid]){...
  • 查找算法-顺序查找、有序查找

    千次阅读 2016-12-06 16:15:44
    1.顺序表的查找 1)顺序查找 顺序查找又称为线性查找,是一种最简单的查找方法。  从表的一端开始,向另一端逐个按要查找的值key 与关键码key进行比较,若找到,查找成功,并给出数据元素在表中的位置;若...
  • 有序数组二分法查找算法) def search(array, num): end = len(array) - 1 # end指向列表最后一位元素的索引 start = 0 # start指向第一位元素的索引 while start <= end: mid = start + (end...
  • 参考教材:http://www.ibeifeng.com/thread-htm-fid-297.html 一共12讲 第二讲:有序数组和查找算法 package ch01;public class MyOrderedArray { // 数组 private long[] arr; // 数组中有效数据的大小 private
  • C语言实现三种有序查找算法

    千次阅读 2017-08-09 16:04:24
    折半查找的基本思想是:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区域继续查找;若给定值大于中间记录的关键字,则在...
  • 如果静态查找表是一个有序表,则可以使用折半查找。  折半查找的过程是:先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。折半查找过程是以处于区间中间位置记录的关键字和给定...
  • 查找算法之二分查找算法

    千次阅读 2015-07-23 08:08:49
    概述二分查找算法也称折半查找算法,是在有序数组中用到的较为频繁的一种查找算法。在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,即顺序查找。二分查找较顺序查找更优,因为...
  • 概要引入折半查找基本概念折半查找java代码实现折半查找算法复杂度分析折半查找改进版1:插值查找折半查找改进版2:斐波那契查找总结 引入 顺序查找虽然算法非常简单,对静态查找表的记录没有任何要求,但是当查找...
  • 折半查找算法介绍折半查找(Binary Search)又称为二分查找。它的前提是线性表中的记录必须是关键码有序(通常从小到大有序),线性表必须采用顺序存储。从算法名称可以看出算法的思路,先取有序序列中间值与查找值...
  • 本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法。分享给大家供大家参考。具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入...
  • 有序查找的三种算法

    千次阅读 2015-03-27 21:50:46
    #include int Binary_Search(int *a,int n, int key) { int low,high,mid; low = 0; high = n; while(low) ... mid = low +(high-low)*(key-a[low])/(a[high] - a[low]);//插值查找 //mid = (low+high)/2
  • 因此,折半查找方法适用于不经常变动而查找频繁的有序列表。 【算法思想】首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置...
  • 有序矩阵查找的快速算法(C++版)

    千次阅读 2015-11-23 22:08:25
    题目: 行和列都排好序的矩阵,请设计一个高效算法,快速查找矩阵中是否含有值x。...思路:判断矩阵右上角元素与待查找元素的大小,利用矩阵行列都有序的特性, 每次取出一行或一列元素。 算法时间复杂度
  • 有序数组的最快的查找算法

    千次阅读 2020-03-20 11:15:17
    有一个有序的数组,有没有最快的方法查找到里面的一个元素是否存在?存在返回下标,不存在返回-1。 部分人回答用循环,多数人想到用数组的findIndex方法。 很少的人知道这个题是要用二分查找的。 这个题主要是想看...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 138,732
精华内容 55,492
关键字:

对于有序列表使用的查找算法