折半查找 订阅
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 [1] 展开全文
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 [1]
信息
外文名
Binary Search
提出时间
1946
别    称
折半查找
提出者
John Mauchly
应用学科
计算机
中文名
二分查找
适用领域范围
编程语言
缺    点
待查表为有序表
优    点
查找速度快
时间复杂度
O(log2n) [1]
二分查找查找过程
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
收起全文
精华内容
下载资源
问答
  • javascript折半查找详解

    2020-12-12 07:51:01
    折半查找法: 在有序表中,把待查找数据值与查找范围的中间元素值进行比较,会有三种情况出现: 1) 待查找数据值与中间元素值正好相等,则放回中间元素值的索引。 2) 待查找数据值比中间元素值小,则以整个查找...
  • 本文实例为大家分享了C语言实现顺序表的顺序查找和折半查找的具体代码,供大家参考,具体内容如下 顺序查找: #include using namespace std; int SeqSearch(int r[],int n,int k) { r[0]=k;//下标0用作哨兵存放...
  • 主要介绍了C++二分查找(折半查找)算法,结合实例形式详细分析了二分查找算法的原理、思想、实现方法与相关操作技巧,需要的朋友可以参考下
  • C语言是一门通用计算机编程语言,广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码
  • 数据结构 折半查找 实例代码: /* 名称:折半查找 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include #include #include <windows> #define N 11 // 数据元素个数 typedef int Key...
  • 第三部:输入一个数,在后在排好序的数中进行折半查找,判断该数的位置 实现代码如下: 方法一: 选择排序法+循环折半查找法 代码如下:#include<iostream>using namespace std;int main(){ int a[15]; int n,i; ...
  • 折半查找算法

    2018-07-26 13:49:43
    前几天做题才想起来的折半查找算法,其实也不难,自己仔细想想也就会了,实在不行就上博客或者是论坛去查询资料就行了。学习编程语言也是这样的呀,遇到不会的就去图书馆或者是网上去查找自己所需要的东西。
  • 包括常见的排序算法,以及折半查找,首先对要查找的数据排好序,然后用递归调用的方式实现折半查找(包括了两种实现方式)。指定一个排好序的数组和要查找的值,同时指定要查找的左边界和有边界。左右边界要位于数组...
  • java实现折半查找算法

    2019-12-06 17:27:55
    所谓的二分查找,指的是将待查的数据序列而分化,然后对比中间中间值和要查找值,判断结果,相等则找到,小于则在左边的子序列找,大于则在右边的子序列找
  • 递归折半查找

    2015-10-05 22:17:40
    二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表...
  • 顺序查找和折半查找

    2018-12-09 11:33:26
    基于《数据结构c语言版 》严蔚敏 自己写的顺序查找和折半查找
  • 折半查找 代码 #include<stdio.h> #include<malloc.h> typedef struct{ int *elem; int length; }sstable; int searchbin(sstable ST,int key) { int low,high,mid; low=1;high=ST.length; while(low) { mid=(low+hi
  • 非递归折半查找

    2018-05-23 13:26:48
    非递归查找的简单C语言程序,供初学者参考一下,哈哈。
  • 定义:折半查找技术,也就是二分查找。它的前提是线性表中的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储。 折半查找的基本思想:取中间记录作为比较对象,若给定值与中间记录的关键字,则在...
  • 使用折半查找,输入一个整数,查找是否在数组中,如在给出下标,否则-1
  • 折半查找代码

    2015-06-14 17:09:52
    折半查找是一种数据结构算法 非常有用 我们用C语言实现了查找 简单有效
  • 摘要:折半查找是采用跳跃跃方式先将顺序数列中的“中间值”与所查询值进行比较,然后按照比值大于或小于“中间值”来判断所查找数的甩在区域。文章给出了将折半算法应用于数字信号处理器上以实现二进制数的查找算法...
  • 折半查找的递归算法

    2015-11-02 09:54:24
    折半查找的递归算法,非常实用,可以实现的C语言程序
  • 今天学了折半查找算法,折半查找是蛮简单的,但是归并排序我就挺懵比,看教材C语言写的归并排序看不懂,后来参考了别人的博客,终于搞懂了。 折半查找 先看下课本对于 折半查找的讲解。注意了,折半查找是对于有序...
  • 折半查找

    2020-09-14 12:55:03
    折半查找又称为二分查找,它使用于有序的顺序表。 二 折半查找的基本思想 折半查找首先将定值key与表中中间位置的元素比较,若相等,则查找成功,并返回该元素的存储位置;若不等,则所需查找到的元素只能在中间...

    一 概述

    折半查找又称为二分查找,它使用于有序的顺序表。

    二 折半查找的基本思想

    折半查找首先将定值key与表中中间位置的元素比较,若相等,则查找成功,并返回该元素的存储位置;若不等,则所需查找到的元素只能在中间元素以外的前半部分或后半部分;例如,在查找表升序排列时,若给定值key大于中间元素,则所查找的元素只可能在后半部分。然后就在缩小的范围内继续进行同样的查找,如此重复,知道找到为止,或确定表中没有所需要查找的元素,则查找失败,返回查找失败的信息。

    折半查找的数据结构:

    int Binary_Search(SeqList L,ElemType key) {
        
        int low = 0,high = L.TableLen-1,mid;
        while(low<=high) {
            mid = (low+high)/2;    //取中间位置
            if(L.elem[mid] == key){
                return mid;        //查找成功则返回所在位置
            }else if(L.elem[mid] > key){
                high = mid - 1;    //从前半部分继续查找
            }else {
                low = high + 1;    //从后半部分继续查找
            }
            return -1;             //查找失败,返回-1
        }
    }

    由此可见,折半查找需要方便的定位查找区域,所以它要求线性表必须具有随机存取的特性。因此,该查找法仅适合于顺序存储结构,不适合于链式存储结构,且要求元素按照关键字有序排列。

    折半查找的时间复杂度为O(log2^n),平均情况下比顺序查找的效率高。

    展开全文
  • NULL 博文链接:https://128kj.iteye.com/blog/1744446
  • 折半查找验证

    2017-10-10 14:48:11
    大学数据结构,折半查找的验证的实现代码,基础基础基础
  • 折半查找算法.ppt

    2019-08-19 09:58:35
    本书是折半查找算法的标准教材,目的是让大家知道好的程序设计和算法分析技巧,难得一见的好书!
  • 主要介绍了PHP有序表查找之二分查找(折半查找)算法,简单介绍了二分查找法的概念、原理并结合实例形式分析了php基于二分查找算法进行有序线性表查找的相关操作技巧,需要的朋友可以参考下

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,511
精华内容 15,804
关键字:

折半查找