`

折半查找

    博客分类:
  • java
阅读更多

http://www.hiahia.org/datastructure/CHAZHAO/chazhao9.2.2.1.htm

二分查找

1、二分查找(Binary Search)
     二分查找又称折半查找,它是一种效率较高的查找方法。
     二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。

2、二分查找的基本思想
     二分查找的基本思想是:(设R[low..high]是当前的查找区间)
(1)首先确定该区间的中点位置:
                
(2)然后将待查的K值与R[mid].key比较:若相等,则查找成功并返回此位置,否则须确定新的查找区间,继续二分查找,具体方法如下:
     ①若R[mid].key>K,则由表的有序性可知R[mid..n].keys均大于K,因此若表中存在关键字等于K的结点,则该结点必定是在位置mid左边的子表R[1..mid-1]中,故新的查找区间是左子表R[1..mid-1]。
     ②类似地,若R[mid].key<K,则要查找的K必在mid的右子表R[mid+1..n]中,即新的查找区间是右子表R[mid+1..n]。下一次查找是针对新的查找区间进行的。
     因此,从初始的查找区间R[1..n]开始,每经过一次与当前查找区间的中点位置上的结点关键字的比较,就可确定查找是否成功,不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点,或者直至当前的查找区间为空(即查找失败)时为止。

3、二分查找算法
    int BinSearch(SeqList R,KeyType K)
      { //在有序表R[1..n]中进行二分查找,成功时返回结点的位置,失败时返回零
        int low=1,high=n,mid; //置当前查找区间上、下界的初值
        while(low<=high){ //当前查找区间R[low..high]非空
          mid=(low+high)/2;
          if(R[mid].key==K) return mid; //查找成功返回
          if(R[mid].kdy>K)
             high=mid-1; //继续在R[low..mid-1]中查找
          else
             low=mid+1; //继续在R[mid+1..high]中查找
         }
        return 0; //当low>high时表示查找区间为空,查找失败
       } //BinSeareh
  二分查找算法亦很容易给出其递归程序【参见练习】

4、 二分查找算法的执行过程
  设算法的输入实例中有序的关键字序列为
    (05,13,19,21,37,56,64,75,80,88,92)
要查找的关键字K分别是21和85。具体查找过程【参见动画演示】 
分享到:
评论

相关推荐

    折半查找(二分查找)折半查找(二分查找)折半查找(二分查找)

    "折半查找(二分查找)" 折半查找(二分查找)是一种高效的查找算法,对于顺序存储的有序表,可以快速地找到指定的关键字记录。该算法的基本思想是,每次比较给定值 K 与中间位置记录的关键字值,并根据比较结果...

    C语言实现顺序表的顺序查找和折半查找

    C语言实现顺序表的顺序查找和折半查找 在计算机科学中,查找是指在一组数据中找到特定元素的过程。顺序表是一种基本的数据结构,在实际应用中非常常见。因此,学习如何在顺序表中实现查找是非常重要的。下面,我们...

    折半查找的递归算法

    ### 折半查找的递归算法 #### 一、引言 折半查找(也称为二分查找)是一种高效的查找算法,适用于有序数组。通过不断将查找区间对半分割,可以快速定位目标值的位置,时间复杂度为O(log n),其中n是数组长度。本文...

    数据结构--折半查找

    数据结构习题---折半查找代码 void BinInsert(int A[],int &n,int item) { int j,low=1,high=n,mid; while(low) { /* 利用折半查找法查找合适位置*/ mid=(low+high)/2; /* 计算当前查找部分的中间位置*/ if...

    折半查找算法在顺序表中插入一个元素讲解.pdf

    折半查找算法在顺序表中插入一个元素讲解 折半查找算法是一种常用的查找算法,它可以在已经排好序的顺序表中快速地找到某个元素。下面我们来详细讲解折半查找算法在顺序表中插入一个元素的过程。 折半查找算法的...

    C#Windows窗体模拟折半查找程序

    **C# Windows窗体模拟折半查找程序** 在C#编程环境中,开发Windows窗体应用程序是一种常见的实践,它允许用户通过图形用户界面(GUI)与软件进行交互。在这个特定的项目中,我们关注的是实现一个模拟折半查找算法的...

    二叉排序树和折半查找

    二叉排序树在查找过程中类似于连续的折半查找,只不过是在树结构中进行,而折半查找是在数组中进行。 8. **应用**: 二叉排序树广泛用于数据库索引、文件系统和虚拟内存管理等场景,而折半查找常用于大量有序数据...

    汇编课程设计 实现折半查找

    在本汇编课程设计中,我们关注的主题是“实现折半查找”,这是一项在计算机科学领域内基础且重要的算法技术。折半查找,也称为二分查找,是一种在有序数组中搜索特定元素的有效方法。其基本思想是通过不断将搜索范围...

    静态查找表。实现有序表的折半查找算法

    ### 静态查找表与折半查找算法 在计算机科学中,静态查找表是一种用于存储数据并能够高效检索特定元素的数据结构。本篇文章将详细解释如何实现一个静态查找表,并利用折半查找算法(也称二分查找算法)来查询表中的...

    折半查找算法及matlab代码实现

    ### 折半查找算法及其MATLAB实现 #### 折半查找算法原理 折半查找算法是一种高效的搜索技术,尤其适用于已经排序的数组。该算法的基本思想是通过不断将搜索范围减半来查找目标值,因此也被称为二分查找。与线性...

    顺序查找和折半查找在10个元素中查找20

    在给定的标题“顺序查找和折半查找在10个元素中查找20”中,我们关注的是两种基本的查找算法:顺序查找(Sequential Search)和折半查找(Binary Search)。这些算法在处理有序或无序数据集时各有优势,下面我们将...

    折半查找算法的改进和程序实现

    折半查找算法是一种在有序数组中寻找特定元素的搜索算法,其基本思想是将数组分为两半,通过比较中间元素和目标值来缩小搜索范围。然而,传统的折半查找在某些情况下并不一定是效率最高的方法。通过对查找算法的改进...

    折半查找 c语言函数

    折半查找,又称二分查找,是一种在有序数组中查找特定元素的搜索算法。它的基本思想是通过比较中间元素和目标值,将搜索范围不断缩小为一半,直到找到目标值或者搜索范围为空。这种方法相对于线性查找有显著的效率...

    java 快速排序 折半查找的界面实现 (递归与分治法)

    快速排序和折半查找是两种在计算机科学中广泛使用的算法,尤其在数据处理和搜索操作中扮演着重要角色。在Java编程中,这两种算法都可以通过递归和分治策略进行实现,以提高效率和可读性。下面我们将深入探讨这两个...

    数据结构实验 折半查找的有关操作

    数据结构实验中的“折半查找”是一种高效的搜索算法,特别适用于已排序的数据集合。这个实验旨在帮助学生理解和掌握如何用C语言实现这种算法,以及在顺序存储结构上进行基本的查找表操作。 实验目的分为两个方面: ...

    顺序查找+折半查找

    这里我们主要探讨两个经典的查找算法:顺序查找和折半查找,它们都是在有序或无序数据集合中寻找特定元素的方法。 **顺序查找**,也称为线性查找,是一种基本的查找算法,适用于任何类型的数据结构,尤其是链表和...

    折半查找的简单C语言算法

    使用折半查找,输入一个整数,查找是否在数组中,如在给出下标,否则-1

    利用折半查找整数m在数组中的位置。

    由N个有序整数组成的数列已放在一维数组中,给定程序MODI1.C中函数fun的功能是:利用折半查找整数m在数组中的位置。若找到,返回其下标值;反之,返回-1。 折半查找的基本算法是:每次查找前先确定数组中待查的范围...

    数据结构实验——折半查找

    折半查找是数据结构中,查找的其中一种。此资源不但包括折半查找的算法,还包括帮助其运行的其他代码,可直接运行以实现折半查找。注:输入数据时,要将数据从大到小依次输入,方可实现折半查找。

    查找问题(顺序查找法, 折半查找法,)基本思想

    查找问题(顺序查找法, 折半查找法,)基本思想:一列数放在数组a(1)---a(n)中,待查找的数放在x 中,把x与a数组中的元素从头到尾一一进行比较查找。用变量p表示a数组元素下标,p初值为1,使x与a(p)比较,如果x不等于a...

Global site tag (gtag.js) - Google Analytics