信息
- 外文名
- Binary Search
- 提出时间
- 1946
- 别 称
- 折半查找
- 提出者
- John Mauchly
- 应用学科
- 计算机
- 中文名
- 二分查找
- 适用领域范围
- 编程语言
- 缺 点
- 待查表为有序表
- 优 点
- 查找速度快
- 时间复杂度
- O(log2n) [1]
二分查找查找过程
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
-
2021-06-03 15:55:57
折半查找的算法思想
折半查找又称二分查找,它仅适用于有序的顺序表。
基本思路是:首先将给定值key与表中中间位置元素的关键字比较,若相等,则查找成功,返回该元素的存储位置;若不等,则所需查找的元素只能在中间元素以外的前半部分或后半部分(例如,在查找表升序排列时,若给定值key大于中间元素的关键字,则所查找的元素只可能在后半部分)。然后在缩小的范围内继续进行同样的查找,如此重复,直到找到为止,或确定表中没有所需要查找的元素,则查找不成功,返回查找失败的信息。
折半查找的实现
typedef struct{ //查找表的数据结构(顺序表) ElemType *elem; //动态数组基址 int TableLen; //表的长度 }SSTable; //折半查找 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=mid+1; //从后半部分继续查找 } return -1; //查找失败,返回-1 }
查找效率分析
因为折半查找需要方便地定位查找区域,所以适合折半查找的存储结构必须具有随机存取的特性。因此,该查找法仅适合于线性表的顺序存储结构,不适合于链式存储结构,且要求元素按关键字有序排列。
从判定树可以看出,查找成功时的查找长度为从根结点到目的结点的路径上的结点数,而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数。
折半查找判定树的构造
折半查找的过程可用二叉树来描述,称为判定树。树中每个圆形结点表示一个记录,结点中的值为该记录的关键字值。
由上述分析可知,用折半查找法查找到给定值的比较次数最多不会超过树的高度。在等概率查找时,查找成功的平均查找长度为
树中最下面的叶结点都是方形的,它表示查找不成功的情况。
每个结点值均大于其左子结点值,且均小于于其右子结点值。
若有序序列有n个元素,则对应的判定树有n个圆形的非叶结点和n+1个方形的叶结点。折半查找的查找效率
h是树的高度,并且元素个数为n时树高h=⌈log2(n+1)⌉。所以,折半查找的时间复杂度为O(log2n),平均情况下比顺序查找的效率高。拓展思考
更多相关内容 -
C语言实现顺序表的顺序查找和折半查找
2020-12-25 21:18:00本文实例为大家分享了C语言实现顺序表的顺序查找和折半查找的具体代码,供大家参考,具体内容如下 顺序查找: #include using namespace std; int SeqSearch(int r[],int n,int k) { r[0]=k;//下标0用作哨兵存放... -
C语言数据结构之 折半查找实例详解
2020-12-31 22:44:06数据结构 折半查找 实例代码: /* 名称:折半查找 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include #include #include <windows> #define N 11 // 数据元素个数 typedef int Key... -
C语言实现折半查找法(二分法)
2020-12-16 22:43:52折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的key在哪一半中,再重复上述步骤知道找到目标key; 注意:折半查找法仅适用于对已有顺序的数组、数据进行操作!!! 很显然,折半查找法相... -
python实现折半查找和归并排序算法
2020-09-21 09:09:40主要介绍了python实现折半查找和归并排序算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下 -
纯C语言:折半查找源码分享
2020-09-04 18:30:52主要介绍了纯C语言:折半查找源码,有需要的朋友可以参考一下 -
C++ 先对数组排序,在进行折半查找
2020-12-26 02:37:04第三部:输入一个数,在后在排好序的数中进行折半查找,判断该数的位置 实现代码如下: 方法一: 选择排序法+循环折半查找法 代码如下:#include<iostream>using namespace std;int main(){ int a[15]; int n,i; ... -
折半查找 减治法-C语言
2020-08-07 12:25:25C语言是一门通用计算机编程语言,广泛应用于底层开发。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码 -
C++二分查找(折半查找)算法实例详解
2020-08-30 13:50:03主要介绍了C++二分查找(折半查找)算法,结合实例形式详细分析了二分查找算法的原理、思想、实现方法与相关操作技巧,需要的朋友可以参考下 -
java实现折半查找算法
2019-12-06 17:27:55所谓的二分查找,指的是将待查的数据序列而分化,然后对比中间中间值和要查找值,判断结果,相等则找到,小于则在左边的子序列找,大于则在右边的子序列找 -
折半查找算法
2018-07-26 13:49:43前几天做题才想起来的折半查找算法,其实也不难,自己仔细想想也就会了,实在不行就上博客或者是论坛去查询资料就行了。学习编程语言也是这样的呀,遇到不会的就去图书馆或者是网上去查找自己所需要的东西。 -
顺序查找和折半查找
2017-12-07 20:43:40用顺序存储结构表示查找表,实现以下运算要求: (1)建立一个整数数据文件 datafile; (2)从文件 datafile 读取数据,并导入一维... (4)先对数组中的元素进行排序,分别用递归和非递归两种方式实现折半查找方法。 -
javascript折半查找详解
2020-12-12 07:51:01折半查找法: 在有序表中,把待查找数据值与查找范围的中间元素值进行比较,会有三种情况出现: 1) 待查找数据值与中间元素值正好相等,则放回中间元素值的索引。 2) 待查找数据值比中间元素值小,则以整个查找... -
JavaScript折半查找(二分查找)算法原理与实现方法示例
2020-12-11 17:41:36本文实例讲述了JavaScript折半查找(二分查找)算法原理与实现方法。分享给大家供大家参考,具体如下: 一、问题描述: 在一个升序数组中,使用折半查找得到要查询的值的索引位置。如: var a=[1,2,3,4,5,6,7,8,9];... -
PHP有序表查找之二分查找(折半查找)算法示例
2020-12-20 03:12:39二分查找技术,又称为折半查找。它的前提是线性表中的记录必须是关键码有序(通常从小到达有序),线性表必须采用顺序存储。 基本思想: 在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则... -
非递归折半查找
2018-05-23 13:26:48非递归查找的简单C语言程序,供初学者参考一下,哈哈。 -
PHP实现的折半查找算法示例
2020-12-20 05:43:09定义:折半查找技术,也就是二分查找。它的前提是线性表中的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储。 折半查找的基本思想:取中间记录作为比较对象,若给定值与中间记录的关键字,则在... -
折半查找的递归与非递归算法
2019-04-14 01:28:00NULL 博文链接:https://128kj.iteye.com/blog/1744446 -
javascript 折半查找字符在数组中的位置(有序列表)
2021-01-19 19:35:56代码如下:/** * 折半查找字符在数组中的位置(有序列表) * @param array 被检索的数组 * @param x 要查找的字符 * @type int * @returns 字符在数组中的位置,没找到返回-1 */ function binarySearch(array,x){ var ... -
折半查找代码
2015-06-14 17:09:52折半查找是一种数据结构算法 非常有用 我们用C语言实现了查找 简单有效 -
折半查找的简单C语言算法
2016-05-13 18:37:10使用折半查找,输入一个整数,查找是否在数组中,如在给出下标,否则-1 -
C语言程序设编写程序在数组中查找一个数要求 ⑴用顺序查找实现 ⑵用折半查找实现。 注:若有该数,则输出该...
2021-05-26 16:23:50C语言程序设计-查找算法:读懂、掌握顺序查找、折半查找算法 编写程序在数组中查找一个数。要求: ⑴用顺序查找实现; ⑵用折半查找实现。 注:若有该数,则输出该数,否则输出“无此数”。 -
C++实现折半查找
2020-12-16 21:33:47本文实例为大家分享了C++实现折半查找的具体代码,供大家参考,具体内容如下 折半查找 定义: 计算机科学中,折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:... -
折半查找的递归算法
2015-11-02 09:54:24折半查找的递归算法,非常实用,可以实现的C语言程序 -
折半查找实例
2018-10-17 21:26:16该程序是一个折半查找的一个具体的例子,其中有对数组的冒泡排序,以及随机数组的产生。 -
C语言折半查找法-综合文档
2021-05-22 05:02:48C语言折半查找法.doc -
JAVA实现排序算法和折半查找
2020-04-08 23:23:34包括常见的排序算法,以及折半查找,首先对要查找的数据排好序,然后用递归调用的方式实现折半查找(包括了两种实现方式)。指定一个排好序的数组和要查找的值,同时指定要查找的左边界和有边界。左右边界要位于数组... -
折半查找main.cpp
2020-06-17 19:23:43折半插入排序(Binary Insertion Sort)是对插入排序算法的一种改进,所谓排序算法过程,就是不断的依次将元素插入前面已排好序的序列中。 排序思想:有一组数据待排序,排序区间为Array[0]~Array[n-1]。将数据分为...