精华内容
下载资源
问答
  • 查找专题查找的概念查找表操作⽅方式分类(静态/动态)顺序表查找(Sequential Search)代码实现优化(增加哨兵,将key存储在a[0])折半查找(Binary Search)代码实现查找范围优化(插值查找)斐波拉契查找(Fibonacci ...

    查找的概念

    查找(Searching): 就是根据给定的某个值,在查找表中确定⼀一个其关键字等于给定值 的数据元素。
    **查找表(Search Table)**是由同一类型的数据元素(记录)构成的集合。
    **关键字(Key)**是数据元素中某个数据项的值.又称为键值. ⽤用它可 以表示一个数据元素,也可以标识一个记录的某个数据项(字段). 我们称为关键码。
    若关键字可以唯一地标识一个记录, 则称此关键字为主关键字 (Primary Key)。
    对于那些可以识别多个属于元素(记录)的关键字,我们称为次关键 字(Secondary Key)。

    查找表操作⽅方式分类(静态/动态)

    静态查找表(Static Search Table): 只作查找操作的查找表;

    1. 查询某个”特定的”数据元素是否在查找表中;

    2. 检索某个"特定的"数据元素和各种属性;

    动态查找表(Dynamic Search Table): 在查找过程中同时插⼊入查找表中不不存在的数据元素, 或者从查找表中删除已经存在的某个数据元素; 显然动态查找表的操作就是2个动作。

    1. 查找时插⼊数据元素;
    2. 查找时删除数据元素;

    顺序表查找(Sequential Search)

    顺序查找(Sequential Search), 又称为线性查找. 是最基本的查找技术. 它的查找过程: 从表中的第一个(或最后一个)记录开始,逐个进行记录关键 字和给定值比较;

    1. 若某个记录的关键字和给定值相等,则查找成功,找到所查记录;
    2. 如果直到最后一个(或第一个)记录, 其关键字和给定值比较都不等 时, 则表中没有所查的记录,查找不成功;
    代码实现
    //1.顺序查找
    //a为数组,n为查找的数组个数,key为要查找的关键字;
    int Sequential_Search(int *a,int n,int key){
        for (int i = 1; i <= n ; i++)
            if (a[i] == key)
                return i;
       
        return 0;
    }
    
    优化(增加哨兵,将key存储在a[0])
    //2.顺序查找_哨兵
    int Sequential_Search2(int *a,int n,int key){
        int i;
        //设置a[0]为关键字值,称为'哨兵'
        a[0] = key;
        //循环从数组尾部开始
        i = n;
        while (a[i] != key) {
            i--;
        }
        //返回0,则说明查找失败
        return i;
    }
    

    折半查找(Binary Search)

    折半查找(Binary Search)技术,又称为二分查找.
    它的前提是线性表中的记录必须是关键码有序(通常是从小到⼤有序),线性表必须采⽤用顺序存储;

    折半查找的基本思想是:

    1. 在有序表中,取中间记录作为⽐较对象,若给定值与中间记录的关键字相 等则查找成功;
    2. 若给定值小于中间的记录关键字,则在中间记录的左半区继续查找;
    3. 若给定的值大于中间记录的关键字,则在中间记录的右半区继续查找;
    4. 不断重复以上的过程,直到查找成功,或所以查找区域⽆记录,查找失败为止.
    代码实现
    //假设数组a,已经是有序的(从小到大)
    int Binary_Search(int *a,int n,int key){
        
        int low,high,mid;
        //定义最低下标为记录首位
        low = 1;
        //定义最高下标为记录末位
        high = n;
        while (low <= high) {
            
            //折半计算
            mid = (low + high) /2;
            
            
            if (key < a[mid]) {
                //若key比a[mid] 小,则将最高下标调整到中位下标小一位;
                high = mid-1;
            }else if(key > a[mid]){
                 //若key比a[mid] 大,则将最低下标调整到中位下标大一位;
                low = mid+1;
            }else
                //若相等则说明mid即为查找到的位置;
                return mid;
        }
        
        return 0;
    }
    
    查找范围优化(插值查找)

    插值查找(Interpolation Search):是根据查找的关键字key 与查找表中最大最⼩记录的关键字⽐比较后的查找方法, 其核心 就是在于插值的计算公式:
    在这里插入图片描述
    #####代码实现

    int Interpolation_Search(int *a,int n,int key){
        int low,high,mid;
        low = 1;
        high = n;
        
        while (low <= high) {
            
            //插值
            mid = low+ (high-low)*(key-a[low])/(a[high]-a[low]);
        
            if (key < a[mid]) {
                //若key比a[mid]插值小,则将最高下标调整到插值下标小一位;
                high = mid-1;
            }else if(key > a[mid]){
                //若key比a[mid]插值 大,则将最低下标调整到插值下标大一位;
                low = mid+1;
            }else
                //若相等则说明mid即为查找到的位置;
                return mid;
        }
        
        return 0;
    }
    

    斐波拉契查找(Fibonacci Search)

    代码实现
    //5.斐波拉契查找
    int F[100]; /* 斐波那契数列 */
    int Fibonacci_Search(int *a,int n,int key){
      
        int low,high,mid,i,k;
        //最低下标为记录的首位;
        low = 1;
        //最高下标为记录的末位;
        high = n;
        k = 0;
        
        //1.计算n为斐波拉契数列的位置;
        while (n > F[k]-1) {
            k++;
        }
        
        //2.将数组a不满的位置补全值;
        for(i = n;i < F[k]-1;i++)
            a[i] = a[n];
        
        //3.
        while (low <= high) {
            
            //计算当前分隔的下标;
            mid = low+F[k-1]-1;
            
            
            if (key < a[mid]) {
                //若查找的记录小于当前分隔记录;
                //将最高下标调整到分隔下标mid-1处;
                high = mid-1;
                //斐波拉契数列下标减1位;
                k = k-1;
                
            }else if(key > a[mid]){
                //若查找的记录大于当前的分隔记录;
                //最低下标调整到分隔下标mid+1处
                low = mid+1;
                //斐波拉契数列下标减2位;
                k = k-2;
                
            }else{
                if (mid <= n) {
                    //若相等则说明,mid即为查找的位置;
                    return mid;
                }else
                {
                    //若mid>n,说明是补全数值,返回n;
                    return n;
                }
            }
        }
        return 0;
    }
    

    有序查找-总结

    这几种查找方式只是每次选择的范围不同,其公式总结如下:
    在这里插入图片描述

    动态查找表

    二叉排序树(Binary Sort Tree)

    二叉排序树(Binary Sort Tree),又称为二叉查找树. 它或者是一颗空树.或者是一颗具有下列性质的二叉树;

    1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结构的值;
    2. 若它的右子树不空,则右子树上的所有结点的值均大于它的根结点的值;
    3. 它的左右子树也分别是二叉排序树;
    ⼆叉排序树(Binary Sort Tree) — 树结构定义

    在这里插入图片描述

    二叉排序树(Binary Sort Tree) — 查找操作代码实现
    //1.二叉排序树--查找
    /*
     递归查找二叉排序树T中,是否存在key;
     指针f指向T的双亲,器初始值为NULL;
     若查找成功,则指针p指向该数据元素的结点,并且返回TRUE;
     若指针p指向查找路径上访问的最后一个结点则返回FALSE;
     */
    Status SearchBST(BiTree T,int key,BiTree f, BiTree *p){
       
        if (!T)    /*  查找不成功 */
        {
            *p = f;
            return FALSE;
        }
        else if (key==T->data) /*  查找成功 */
        {
            *p = T;
            return TRUE;
        }
        else if (key<T->data)
            return SearchBST(T->lchild, key, T, p);  /*  在左子树中继续查找 */
        else
            return SearchBST(T->rchild, key, T, p);  /*  在右子树中继续查找 */
    }
    
    二叉排序树(Binary Sort Tree) — 插入操作代码实现
    //2.二叉排序树-插入
    /*  当二叉排序树T中不存在关键字等于key的数据元素时, */
    /*  插入key并返回TRUE,否则返回FALSE */
    Status InsertBST(BiTree *T, int key) {
        
        BiTree p,s;
        //1.查找插入的值是否存在二叉树中;查找失败则->
        if (!SearchBST(*T, key, NULL, &p)) {
            
            //2.初始化结点s,并将key赋值给s,将s的左右孩子结点暂时设置为NULL
            s = (BiTree)malloc(sizeof(BiTNode));
            s->data = key;
            s->lchild = s->rchild = NULL;
            
            //3.
            if (!p) {
                //如果p为空,则将s作为二叉树新的根结点;
                *T = s;
            }else if(key < p->data){
                //如果key<p->data,则将s插入为左孩子;
                p->lchild = s;
            }else
                //如果key>p->data,则将s插入为右孩子;
                p->rchild = s;
            
            return  TRUE;
        }
        
        return FALSE;
    }
    
    二叉排序树(Binary Sort Tree) — 删除操作
    //3.从二叉排序树中删除结点p,并重接它的左或者右子树;
    Status Delete(BiTree *p){
        
        BiTree temp,s;
        
        
        if((*p)->rchild == NULL){
           
            //情况1: 如果当前删除的结点,右子树为空.那么则只需要重新连接它的左子树;
            //①将结点p临时存储到temp中;
            temp = *p;
            //②将p指向到p的左子树上;
            *p = (*p)->lchild;
            //③释放需要删除的temp结点;
            free(temp);
            
        }else if((*p)->lchild == NULL){
            
            //情况2:如果当前删除的结点,左子树为空.那么则只需要重新连接它的右子树;
            //①将结点p存储到temp中;
            temp = *p;
            //②将p指向到p的右子树上;
            *p = (*p)->rchild;
            //③释放需要删除的temp结点
            free(temp);
        }else{
            
            //情况③:删除的当前结点的左右子树均不为空;
           
            //①将结点p存储到临时变量temp, 并且让结点s指向p的左子树
            temp = *p;
            s = (*p)->lchild;
          
            //②将s指针,向右到尽头(目的是找到待删结点的前驱)
            //-在待删除的结点的左子树中,从右边找到直接前驱
            //-使用`temp`保存好直接前驱的双亲结点
            while (s->rchild) {
                temp = s;
                s = s->rchild;
            }
            
            //③将要删除的结点p数据赋值成s->data;
            (*p)->data = s->data;
            
            //④重连子树
            //-如果temp 不等于p,则将S->lchild 赋值给temp->rchild
            //-如果temp 等于p,则将S->lchild 赋值给temp->lchild
            if(temp != *p)
                temp->rchild = s->lchild;
            else
                temp->lchild = s->lchild;
            
            //⑤删除s指向的结点; free(s)
            free(s);
        }
        
        return  TRUE;
    }
    
    插入删除代码综合
    //4.查找结点,并将其在二叉排序中删除;
    /* 若二叉排序树T中存在关键字等于key的数据元素时,则删除该数据元素结点, */
    /* 并返回TRUE;否则返回FALSE。 */
    Status DeleteBST(BiTree *T,int key)
    {
        //不存在关键字等于key的数据元素
        if(!*T)
            return FALSE;
        else
        {
            //找到关键字等于key的数据元素
            if (key==(*T)->data)
                return Delete(T);
            else if (key<(*T)->data)
                //关键字key小于当前结点,则缩小查找范围到它的左子树;
                return DeleteBST(&(*T)->lchild,key);
            else
                //关键字key大于当前结点,则缩小查找范围到它的右子树;
                return DeleteBST(&(*T)->rchild,key);
            
        }
    }
    
    展开全文
  • 常见的排序方法有哪些

    千次阅读 2018-06-29 16:11:20
    大家好,我是IT修真院郑州分院第八期的学员,今天给大家分享一下,题目常见的排序方法有哪些。 一、背景介绍 排序算法(英语:Sorting algorithm)是一种能将一串资料依照特定排序方式进行排列的一种算法。最常...

    大家好,我是IT修真院郑州分院第八期的学员,今天给大家分享一下,题目常见的排序方法有哪些。


    一、背景介绍

    排序算法(英语:Sorting algorithm)是一种能将一串资料依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。

    查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。 所以在面试中经常会问到排序算法及其相关的问题。

     

    二、知识剖析

    常见的排序算法:冒泡排序、快速排序和归并排序。

     

    冒泡排序

    算法原理:冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换时,此时该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    具体算法描述:

    1.   比较相邻的元素。如果第一个比第二个大,就交换它们两个;

    2.   对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;

    3.   针对所有的元素重复以上的步骤,除了最后一个;

    4.   重复步骤 1 31 3,直到排序完成。

     

    快速排序

    算法原理:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

    具体算法描述:

    1.   从数列中挑出一个元素,称为 “基准”(pivot);

    2.   重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

    3.   递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

     

    归并排序

    算法原理:归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

    具体算法描述:

    1.   把长度为 n 的输入序列分成两个长度为 n/2 的子序列;

    2.   对这两个子序列分别采用归并排序;

    3.   将两个排序好的子序列合并成一个最终的排序序列。


    三、常见问题

    如何在js中实现上述算法?


    四、 解决方案

    视频

    五、编码实战

     PPT


    六、拓展思考

    原生js中有自带的排序的函数sort(),angularjs中排序的方法是自带的过滤器orderby

     

    七、参考文献

    参考:js排序算法汇总

     


    八、更多讨论

    讨论一:各排序方法的的时间复杂度比较?

    排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
    冒泡排序 O(n2)O(n2) O(n)O(n) O(n2)O(n2) O(1)O(1) 内排序 稳定
    选择排序 O(n2)O(n2) O(n2)O(n2) O(n2)O(n2) O(1)O(1) 内排序 不稳定
    插入排序 O(n2)O(n2) O(n)O(n) O(n2)O(n2) O(1)O(1) 内排序 稳定
    希尔排序 O(nlogn)O(nlog⁡n) O(n(log22n))O(n(log22⁡n)) O(n(log22n))O(n(log22⁡n)) O(1)O(1) 内排序 不稳定
    归并排序 O(nlogn)O(nlog⁡n) O(nlogn)O(nlog⁡n) O(nlogn)O(nlog⁡n) O(n)O(n) 外排序 稳定
    快速排序 O(nlogn)O(nlog⁡n) O(nlogn)O(nlog⁡n) O(n2)O(n2) O(logn)O(log⁡n) 内排序 不稳定
    堆排序 O(nlogn)O(nlog⁡n) O(nlogn)O(nlog⁡n) O(nlogn)O(nlog⁡n) O(1)O(1) 内排序 不稳定
    计数排序 O(n+k)O(n+k) O(n+k)O(n+k) O(n+k)O(n+k) O(k)O(k) 外排序 稳定
    桶排序 O(n+k)O(n+k) O(n+k)O(n+k) O(n2)O(n2) O(n+k)O(n+k) 外排序 稳定
    基数排序 O(n×k)O(n×k) O(n×k)O(n×k) O(n×k)O(n×k) O(n+k)O(n+k) 外排序 稳定

    数据量小的时候快速排序最快,归并排序其次,冒泡排序最次;数据大的情况的下归并排序的性能超过快速排序。归并排序的稳定性是三者之中最好的。讨论二:三个排序哪个效率最高?

    讨论三:怎么判断一个排序算法的好坏?

    首先要保证其正确性,在正确性的基础上比较其代码可读性,时间复杂度,空间复杂度,稳定性。

    感谢大家观看!

    今天的分享就到这里啦,欢迎大家点赞、转发、留言、拍砖~

    展开全文
  • 面试中被问到关于算法的题目:有哪些常见的查找算法?下来就把我所掌握的查找算法分享给大家,本文主要介绍二分查找算法。 算法定义(摘自百度):二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能...

        不知不觉在目前的公司待满3年了,打算回家找份工作。面试中被问到关于算法的题目:有哪些常见的查找算法?下来就把我所掌握的查找算法分享给大家,本文主要介绍二分查找算法。

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

        上述定义可以看到这种二分查找算法是基于一个有序序列的算法,因此仅适用于已经排好顺序的情况下使用,否则需要先对序列进行排序。

        下面用Java代码来描述两种形式的二分查找算法:

         一、递归二分查找算法

     1 package algorithm;
     2 
     3 /**
     4  * 题目: 现有一个int型数组,其元素顺序排列。现给出一个数字,返回其在数组中的下标,如不存在返回-1.
     5  *
     6  */
     7 public class BinarySearch {
     8 
     9     // 用来记录查找次数
    10     private static int count = 0;
    11 
    12     /**
    13      * 
    14      * @param number
    15      *            待查找数字
    16      * @param array
    17      *            待查找数组
    18      * @return 数组下标或-1
    19      */
    20     public static int getIndex(int number, int[] array) {
    21         count = 0;
    22         if (array == null || array.length == 0) { // 如果数组对象为空或者数组元素个数为0,直接返回-1
    23             count++;
    24             return -1;
    25         }
    26         return binarySearch(0, array.length - 1, array, number); // 调用递归方法
    27     }
    28 
    29     /**
    30      * 
    31      * @param startIndex
    32      *            起始下标
    33      * @param endIndex
    34      *            结束下标
    35      * @param array
    36      *            数组
    37      * @param number
    38      *            待查找数字
    39      * @return 数组下标或-1
    40      */
    41     private static int binarySearch(int startIndex, int endIndex, int[] array, int number) {
    42         count++;
    43         // startIndex大于endIndex,说明已查找完成但并未查找到number
    44         if (startIndex > endIndex) {
    45             return -1;
    46         }
    47         // 获取中间元素下标
    48         int index = (startIndex + endIndex) / 2;
    49         // 获取中间元素数值
    50         int _number = array[index];
    51         // 比较中间元素与待查找数字
    52         if (_number < number) {
    53             // 如果中间元素数值小与待查找数字,则将查找范围缩小至 起始下标+1~中间元素下标
    54             return binarySearch(index + 1, endIndex, array, number);
    55         } else if (_number > number) {
    56             // 如果中间元素数值大与待查找数字,则将查找范围缩小至 中间元素下标~中间元素下标-1
    57             return binarySearch(startIndex, index - 1, array, number);
    58         }
    59         return index;
    60     }
    61 
    62     public static int getCount() {
    63         return count;
    64     }
    65 
    66 }

     

     

        二、非递归二分查找算法:

     1 package algorithm;
     2 
     3 public class BinarySearchNonRecursive {
     4 
     5     // 记录循环次数
     6     private static int count = 0;
     7 
     8     public static int getIndex(int number, int[] array) {
     9 
    10         // 判断数组是否为空,判断数组长度
    11         if (array == null || array.length == 0) {
    12             return -1;
    13         }
    14 
    15         // 初始化起始下标、结束下标、返回值
    16         int startIndex = 0;
    17         int endIndex = array.length - 1;
    18 
    19         while (startIndex <= endIndex) {
    20             count++;
    21             int middleIndex = (startIndex + endIndex) / 2;
    22             int _number = array[middleIndex];
    23 
    24             if (_number < number) {
    25                 // _number小于number,下次循环查找的起始下标为middleIndex + 1;
    26                 startIndex = middleIndex + 1;
    27             } else if (_number > number) {
    28                 // _number大于number,下次循环查找的结束下标为middleIndex - 1;
    29                 endIndex = middleIndex - 1;
    30             } else {
    31                 // _number等于number,查找到数字,返回结果
    32                 return middleIndex;
    33             }
    34         }
    35 
    36         // 当startIndex > endIndex时,说明未查找到数字。结束循环,返回-1
    37         return -1;
    38 
    39     }
    40 
    41     public static int getCount() {
    42         return count;
    43     }
    44 
    45 }

     

        下面是测试代码:

     1 package algorithm;
     2 
     3 import org.junit.Before;
     4 import org.junit.Test;
     5 
     6 public class BinarySearchTest {
     7 
     8     private int[] array;
     9     private int[] testArray;
    10 
    11     @Before
    12     public void setUp() throws Exception {
    13         array = new int[] { 1, 2, 3, 9, 15, 26, 37, 48, 69, 110, 116, 117, 244, 374, 529 };
    14         testArray = new int[] { 1, 5, 3, 9, 37, 48, 22, 69, 244, 529, -888 };
    15     }
    16 
    17     @Test
    18     public void test() {
    19 
    20         System.out.println("====递归二分查找算法====");
    21         for (int i = 0; i < testArray.length; i++) {
    22             System.out.println("测试数值为 : " + testArray[i]);
    23 
    24             int result = BinarySearch.getIndex(testArray[i], array);
    25 
    26             System.out.println("查找结果为 : " + result);
    27             System.out.println("查询次数 : " + BinarySearch.getCount() + "\n");
    28 
    29         }
    30         System.out.println("\n====非递归二分查找算法====");
    31         for (int i = 0; i < testArray.length; i++) {
    32             System.out.println("测试数值为 : " + testArray[i]);
    33 
    34             int result = BinarySearchNonRecursive.getIndex(testArray[i], array);
    35 
    36             System.out.println("查找结果为 : " + result);
    37             System.out.println("循环次数 : " + BinarySearchNonRecursive.getCount() + "\n");
    38 
    39         }
    40 
    41     }
    42 
    43 }

     

        输出测试结果:

    ====递归二分查找算法====
    测试数值为 : 1
    查找结果为 : 0
    查询次数 : 4
    
    测试数值为 : 5
    查找结果为 : -1
    查询次数 : 5
    
    测试数值为 : 3
    查找结果为 : 2
    查询次数 : 4
    
    测试数值为 : 9
    查找结果为 : 3
    查询次数 : 2
    
    测试数值为 : 37
    查找结果为 : 6
    查询次数 : 4
    
    测试数值为 : 48
    查找结果为 : 7
    查询次数 : 1
    
    测试数值为 : 22
    查找结果为 : -1
    查询次数 : 5
    
    测试数值为 : 69
    查找结果为 : 8
    查询次数 : 4
    
    测试数值为 : 244
    查找结果为 : 12
    查询次数 : 4
    
    测试数值为 : 529
    查找结果为 : 14
    查询次数 : 4
    
    测试数值为 : -888
    查找结果为 : -1
    查询次数 : 5
    
    
    ====非递归二分查找算法====
    测试数值为 : 1
    查找结果为 : 0
    循环次数 : 4
    
    测试数值为 : 5
    查找结果为 : -1
    循环次数 : 4
    
    测试数值为 : 3
    查找结果为 : 2
    循环次数 : 4
    
    测试数值为 : 9
    查找结果为 : 3
    循环次数 : 2
    
    测试数值为 : 37
    查找结果为 : 6
    循环次数 : 4
    
    测试数值为 : 48
    查找结果为 : 7
    循环次数 : 1
    
    测试数值为 : 22
    查找结果为 : -1
    循环次数 : 4
    
    测试数值为 : 69
    查找结果为 : 8
    循环次数 : 4
    
    测试数值为 : 244
    查找结果为 : 12
    循环次数 : 4
    
    测试数值为 : 529
    查找结果为 : 14
    循环次数 : 4
    
    测试数值为 : -888
    查找结果为 : -1
    循环次数 : 4

        从console内容可以看出,两种不同形式二分查找算法的结果是相同的。

        注:一些情况下同样的测试数据,递归二分查找和非递归二分查找的执行次数不一致,这是因为在非递归二分查找算法中,当startIndex>endIndex时,没有进入while语句中,count没有自增;而在递归二分查找算法中,startIndex>endIndex作为一个结束条件,是在递归函数内部判断的,因此记录调用递归函数次数的count自增。这里笔者没有对执行count++的位置进行特殊处理,是为了更好的体现出两种形式的算法的执行步骤。

        总结:两种形式的二分查找算法本质思想都是一样的,即每次将查找数据与中间元素对比大小,未匹配则缩小二分之一的查找范围,直到最终查找到元素或返回未查找到结果。

        最后,希望本文能帮助到有需要的朋友,同时也欢迎大家批评指正文中的不足之处。

     

    转载于:https://www.cnblogs.com/zfLee/p/5654296.html

    展开全文
  • 查找算法小结

    2020-02-01 22:04:46
    那么常见的查找方法有哪些,怎么能够实现又好又快的查找方式呢?下面来做一个小结 1.遍历,顺序查找 如果数据没有任何特点可言,要在一堆数据比如一个一维数组中查找一个特定的数据,此一维数组没有规律。那么很自然...

    项目github地址:bitcarmanlee easy-algorithm-interview-and-practice
    欢迎大家star,留言,一起学习进步

    前言

    对数据进行查找是数据处理中一个最基本最常见同时也最重要的操作。那么常见的查找方法有哪些,怎么能够实现又好又快的查找方式呢?下面来做一个小结

    1.遍历,顺序查找

    如果数据没有任何特点可言,要在一堆数据比如一个一维数组中查找一个特定的数据,此一维数组没有规律。那么很自然想到的方法就是遍历该一维数组,然后与特定数据进行比较看是否相同。

    时间复杂度分析
    该特定数据有可能再数组开头,也有可能再数组的末尾,那么遍历数组的话最少需要1次,最多需要n次,平均则为(1+n)/2次,所以时间复杂度为O(n)。

    2.二分查找

    上面的顺序查找当然是最简单粗暴也是效率最低的一种方式,其本质原因是数组没有任何特点,数据杂乱无章,所以我们没有较好的办法进行优化。那如果原始数据排列比较有特点,我们是不是可以有更好的方式?
    哈佛的计算机公开课视频中,主讲的老师一开场有个很生动的例子,就是给学生一本字典查某个特定的名字在字典中的哪一页。大家想想字典的数据有什么特点?字典的数据,是按照字母序升序排列的。所以如果去查找一个人名字的时候,我们先翻到字典中间位置,如果此时该名字的字母序比字典中间位置的字母序大,那说明名字必出现在字典前半部分,那么我们去前半部分查,反之则去后半部分查。以此类推,一直到查到名字为止。
    时间复杂度分析:
    用二分查找时,最少需要查一次,最多需要log(n+1)次,平均时间复杂度为O(log(n)),比顺序查找的O(n)效率高很多
    所以,二分查找的优点为效率高,缺点是要求原始数据有序。

    3.Hash

    hash又叫散列,他的原理是根据关键字的key值,通过hash算法将key值映射到表中的某一个位置得到value值,从而在查找的时候可以实现快速查找的目的。这个映射函数叫做散列函数,存放(key,value)对的数据结构则被称为散列表。

    java中hash的典型实现有HashMap,关于HashMap的分析有很多,在这里不再阐述。稍微提一下的是,HashMap的冲突解决方式,在jdk1.8之前是使用的拉链法的形式,即如果不同的key映射到了同一个位置,后面会使用一个链表将这些key组织起来。从jdk1.8开始,当链表的长度超过阈值以后,链表会转换成红黑树。

    时间复杂度分析
    哈希表寻址容易,插入删除也相对容易。如果散列函数设计良好没有冲突,理论上可以达到O(1)的时间复杂度。
    但是哈希表如果扩容,会耗费大量的空间与性能,同时散列函数可能也需要重新设计。另外,Hash表中的数据也是无序的。

    所以综合上面的特点来看,如果预先能估算数据的大小,有足够的空间存储哈希表,且不要求数据有序,此时哈希表是个不错的选择。因为哈希表的查找,插入,删除都是O(1)复杂度(不考虑冲突)。

    4.BST(Binary Search Tree)

    排序二叉树与普通二叉树的区别在于:每一个节点记录一个数据,同时满足左分支的数据都小于右分支的数据。
    从查找过程看,排序二叉树与二分查找相似,都是O(log(n))的时间复杂度。
    为了维护排序二叉树的有序性,二叉排序树不需要挪动节点,只需要修改指针可以完成插入和删除的操作,平均耗时O(log(n))。而如果是线性表比如数组,需要的时间复杂度为O(n)。

    所以当有序表是静态查找表时,适宜用顺序表如数组作为其存储结构,而采用二分查找实现其查找操作;若有序表是动态查找表,经常有增加与删除节点的操作,则可以选择排序二叉树作为其数据存储结构。

    展开全文
  • 但是对于公众号这种文章,就算整理了还是一些局限性,因为没有书签那种折叠功能,为了方便大家定位查找,我这里先列个大纲。整理顺序大概是一. 经验/经历相关文章 二. 数据结构与算法 1. 基础数据结构 2...
  • 那么有哪些查询算法可以使查询速度变得更快呢?顺序查找(linear search )最基本查询算法当然是顺序查找(linear search),也就是对比每个元素方法,不过这种算法在数据量很大时效率是极低。•数据结构:...
  • 常见的散列函数有哪些?冲突又怎么解决喃?散列表的动态扩容解答+面试题一、散列表(哈希表、Hash 表)不同与之前我们介绍的线性表,所有的数据都是顺序存储,当我们需要在线性表中查找某一数据时,当线性表过长,需要...
  • 综述:数据结构和算法对于前端人员来说很重要,特别是一线大厂,将常见的问题做一个总结,巩固自己的知识 前端必须了解的数据结构和算法知识: ...1.去重的方法有哪些?越多越好,扩宽自己的知识面? ...
  • 这次我们来总结一下关于哈希表知识,首先我们要了解什么是哈希表,哈希函数构造思路有哪些?怎么解决哈希冲突?最后再去分析一下哈希查找算法。 哈希表概念 前提小知识 什么是哈希表? 哈希表四个概念 ...
  • 互联网公司最常见的面试算法有哪些?|3.TOP INTERVIEW QUESTIONS (热门面试问题)|4.模拟|1)加油站|2)LRU缓存机制|3)快乐数|4)生命游戏|5)两整数之和|6)FIZZ BUZZ|5.数组|1)乘积最大子序列|2)求众数|3)旋转数组|4...
  • 提问:常见索引有哪些? 1、从数据结构角度 * B-Tree/B+Tree索引:B-Tree/B+Tree简介。 * Hash索引:1、查询效率非常高,一次查询即可;2、仅能满足=、in,不能用于范围查询;3、* 只有memory引擎显示支持。 * 全文...
  • 具体有哪些数据结构,又有哪些算法?  数据结构是数据在计算机内存或者外存中组织方式,算法就是计算机操作数据结构中数据方式方法,比如查找、排序。 很少有数据结构是为了节省存储空间,数据结构和算法...
  • 想好好学习数据结构和算法方面的知识,买的书还没到,先预热一下看看要学习哪些知识,先看看常见的数据结构与算法有哪些 一.线性表 ·数组实现 ·链表 二.栈与队列 三.树与二叉树 ·树 ·二叉树基本概念 ...
  • 常见的策略三种:先进先出策略 FIFO(First In,First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。 设计思路:我们维护一个有序单链表,越靠近链表尾部的...
  • 1.Java容器有哪些? Java容器类库定义了两个不同概念容器:Collection和Map a.Collection 一个独立元素序列,这些元素都服从一条或多条规则。List必须按照插入顺序保存元素;Set不能有重复元素;Queue按照...
  • 常见数据结构的查找、插入、删除时间复杂度 二叉树(Binary Tree) 存储结构 二叉树的存储结构两种,顺序存储结构和链式存储结构。 PS:链式存储结构的二叉树极端情况下会退化成线性链表。 几种特殊二叉树 完全...
  • 数据结构 哈希表.ppt

    2020-08-03 05:01:37
    上章回顾 e常见的排序算法有哪些 e其中那种算法的效率最高 对大量的数据进行排序的化最好使用那种排 序算法 第七章 哈希泰 本章结构 什么是哈希表 哈希表 哈希函数的构造方法 处理冲突的方法 课程目标 e了解什么是...
  • 数据库索引数据结构——B-树/B+树

    千次阅读 2018-08-14 20:28:39
    那么有哪些查询算法可以使查询速度变得更快呢? 1. 顺序查找(linear search ) 最基本查询算法当然是顺序查找(linear search),也就是对比每个元素方法,不过这种算法在数据量很大时效率是极低。 实例...
  • 一些有意思问题

    2017-11-21 15:59:00
    问题:互联网公司最常见的面试算法有哪些? 文章:你真的会写二分查找吗 分治算法 宽度优先搜索 深度优先搜索 回溯法 双指针 c语言中会有描述 动态规划 扫描线 快排 性能与CPU,内存,...

空空如也

空空如也

1 2 3
收藏数 58
精华内容 23
关键字:

常见的查找算法有哪些