精华内容
下载资源
问答
  • VB编程:对数组进行二分查找-29

    千次阅读 2016-11-29 09:54:03
    程序代码 Option Explicit Dim myarray(100) As Integer    '定义数组,下标0-100,数组元素为101个 Private Sub Command1_Click()  Dim low, high, mid, n As Integer  Dim found As Boolean  ...
    运行效果
    VB编程:对数组进行二分查找-29

    程序代码
    Option Explicit
    Dim myarray(100) As Integer           '定义数组,下标0-100,数组元素为101个

    Private Sub Command1_Click()
        Dim low, high, mid, n As Integer
        Dim found As Boolean
        low = 0
        n = 0
        high = UBound(myarray)
        found = False
        mid = CInt((high + low) / 2)      '转换为整型,小数部分四舍五入,避免下标出现小数
        Do While Not found And (high >= low)
            n = n + 1
            If CInt(Text1.Text) = myarray(mid) Then   ''查找值和当前中间值比较,相等输出
                found = True
                Label1.Caption = "查询次数:" & n & vbCrLf & _
                                 "查询数值:" & myarray(mid) & vbCrLf & _
                                 "数组下标:" & mid
                Exit Do
            ElseIf CInt(Text1.Text) < myarray(mid) Then  '查找值和当前中间值比较,小了
                high = mid - 1
            Else                                   '查找值和当前中间值比较,大了
                low = mid + 1
            End If
        mid = CInt((high + low) / 2)
        Loop
    End Sub

    Private Sub Form_load()
     Dim i As Integer
        For i = 0 To UBound(myarray)                '给数组赋值
            myarray(i) = i
            Print myarray(i)
        Next i
    End Sub

    学习心得
    1、二分法查找的思想就是:先取中间值作比较,看大了还是小了,大了就往下取数,小了就往上取数。这样逐步缩小查找范围,就不用每个数都去做比较。适用于有序数组,确实能提高计算效率,是一个很不错的思维方式。

    展开全文
  • 二分查找(英语:binary search),也叫折半查找(英语:half-interval search),是一种在有序数组中查找特定元素的搜索算法。所以,二分查找的前提是数组必须是有序的。 时间复杂度、空间复杂度请参照下图(图片...

    算法概述#
    二分查找(英语:binary search),也叫折半查找(英语:half-interval search),是一种在有序数组中查找特定元素的搜索算法。所以,二分查找的前提是数组必须是有序的。
    时间复杂度、空间复杂度请参照下图(图片来自wikipedia):
    在这里插入图片描述

    适用情况#
    二分查找只适用顺序存储结构。为保持表的有vb.net教程序性,在顺序结构里插入和删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。

    对那些查找少而又经常需要改动的线性表,可采用c#教程链表作存储结构,进行顺序查找。链表上无法实现二分查找(更准确的说链表上使用二分查找得不偿失)。

    算法原理#
    二分查找的基本思想是:

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

    算法实现(C#)#
    算法基于C#编写,有简单和泛型两种实现,每种实现又分递归版本、While循环版本。实际运用时,推荐使用While循环版本的二分查找。
    算法代码如下:

    //此算法假定数组已排序;如果不是这样,则结果将不正确。
    class BinarySearch
    {
        //不要使用mid = (high + low) / 2,可能会导致运算溢出
        #region 简单
        // 递归版本           
        public static int Recursive(int[] ary, int target)
        {
            return Recursive(ary, 0, ary.Length-1, target);           
        }
        static int Recursive(int[] ary, int low, int high, int target)
        {
            if (high < low) return -1;    
            int mid = low + ((high - low) >> 1);
            if (ary[mid] == target) return mid;
            if (ary[mid] > target)
            {
                return Recursive(ary, low, mid-1, target);
            }
            else
            {
                return Recursive(ary, mid + 1, high, target);
            }            
        }
        //While循环版本
        public static int WhileLoop(int[] ary, int target)
        {
            int low = 0; 
            int high = ary.Length - 1;
            while (low <= high)
            {                                
                int mid = low + ((high - low) >> 1);
                if (ary[mid] == target) return mid;
                if (ary[mid] > target)
                {
                    high = mid - 1;
                }
                else 
                {
                    low = mid + 1;
                }
            }
            return -1;
        }
        #endregion
        
        #region 泛型
        // 递归版本           
        public static int RecursiveT<T>(T[] ary, T target) where T : IComparable
        {
            return RecursiveT(ary, 0, ary.Length - 1, target);
        }
        static int RecursiveT<T>(T[] ary, int low, int high, T target) where T : IComparable
        {               
            if (high < low) return -1;            
            int mid = low + ((high - low) >> 1);
            int cr = Comparer.Default.Compare(ary[mid], target);             
            if(cr==0)return mid;
            if (cr > 0)
            {
                return RecursiveT(ary, low, mid - 1, target);
            }
            else 
            {
                return RecursiveT(ary, mid + 1, high, target);
            }            
        }
        //While循环版本
        public static int WhileLoopT<T>(T[] ary, T target) where T : IComparable
        {
            int low = 0;
            int high = ary.Length - 1;
            while (low <= high)
            {                
                int mid = low + ((high - low) >> 1);
                int cr = Comparer.Default.Compare(ary[mid], target);                
                if (cr == 0) return mid;
                if (cr>0)
                {
                    high = mid - 1;
                }
                else 
                {
                    low = mid + 1;
                }               
            }
            return -1;
        }
        //默认情况下推荐使用While循环版本
        public static int DefaultT<T>(T[] ary, T target) where T : IComparable 
        {            
            return WhileLoopT(ary, target);
        }
        #endregion 
    }
    
    

    测试代码如下:

    //数组必须有序
    //此处用升序递增的整数数组是为了便于检查结果
    int[] ary = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 }; 
    long[] aryT = new long[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };            
    int target = 8;
    int r = BinarySearch.Recursive(ary, target);
    int w = BinarySearch.WhileLoop(ary, target);
    int rT = BinarySearch.RecursiveT(ary, target);
    int wT = BinarySearch.WhileLoopT(ary, target);
    Console.WriteLine("r={0} w={1} rT={2} wT={3}", r, w, rT, wT);
    

    实际应用:用二分查找法找寻边界值#
    在集合中找到一个大于(小于)目标数t的数x,使得集合中的任意数要么大于(小于)等于x,要么小于(大于)等于t。
    举例来说:给予数组和目标数

    int array = {2, 3, 5, 7, 11, 13, 17};
    int target = 7;
    那么上界值应该是11,因为它“刚刚好”大于7;下界值则是5,因为它“刚刚好”小于7。

    该问题不能直接使用二分查找的实现代码解决,需要对代码做一些修改,但解题思路还是二分查找。

    实现代码如下:

    //用二分查找法找寻上界
    static int BSearchUpperBound(int[] ary, int target)
    {           
        int low = 0;
        int high = ary.Length - 1;            
        while (low <= high)
        {
            int mid = low + ((high - low) >> 1);
            if (high == low) 
            {
                if (ary[mid] > target) return mid;
                else return -1;            
            }
            if (ary[mid] > target)
            {
                //当前找到的数大于目标数时,它可能就是我们要找的数,所以需要保留这个索引
                high = mid ;
            }
            else
            {
                //当前找到的数小于等于目标数时继续向上取区间
                low = mid + 1;
            }
        }
        return -1;        
    }
     //用二分查找法找寻下界
    static  int BSearchLowerBound(int[] ary, int target)
    {
        int low = 0;
        int high = ary.Length - 1;
        while (low <= high)
        {
            //取中间索引时使用向上取整,否则low无法往上爬到下界值
            int mid = low + ((high - low + 1) >> 1);
            if (high == low)
            {
                if (ary[mid] < target) return mid;
                else return -1;
            }               
            if (ary[mid] >= target)
            {
                //当前找到的数大于等于目标数时继续向下取区间
                high = mid-1;
            }
            else
            {
                //当前找到的数小于目标数时,它可能就是我们要找的数,所以需要保留这个索引
                low = mid;
            }
        }
        return -1;
    }
    

    测试代码如下:

    //寻找边界值
    int[] array =new int[]{ 2, 3, 5, 7, 11, 13, 17 };
    int target =6;
    //用二分查找法找寻上届
    int up = BSearchUpperBound(array, target);
    int lo=BSearchLowerBound(array, target);
    参考文章#
    二分搜索(Binary_Search)——简书
    binary search——百度百科
    BinarySearch——.NET源码
    二分查找BinarySearch原理分析、判定树、及其变种——CSDN
    二分查找法的实现和应用汇总——CSDN

    作者: time-flies

    出处:https://www.cnblogs.com/timefiles/p/BinarySearch.html

    展开全文
  • 程序代码 Option Explicit Dim myarray(100) As Integer '定义数组,下标0-100,数组元素为101个 Private Sub Command1_Click() Dim low, high, mid, n As Integer Dim found As Boolean low = 0 ...
    运行效果
    VB编程:对数组进行二分查找-29

    程序代码
    Option Explicit
    Dim myarray(100) As Integer           '定义数组,下标0-100,数组元素为101个

    Private Sub Command1_Click()
        Dim low, high, mid, n As Integer
        Dim found As Boolean
        low = 0
        n = 0
        high = UBound(myarray)
        found = False
        mid = CInt((high + low) / 2)      '转换为整型,小数部分四舍五入,避免下标出现小数
        Do While Not found And (high >= low)
            n = n + 1
            If CInt(Text1.Text) = myarray(mid) Then   ''查找值和当前中间值比较,相等输出
                found = True
                Label1.Caption = "查询次数:" & n & vbCrLf & _
                                 "查询数值:" & myarray(mid) & vbCrLf & _
                                 "数组下标:" & mid
                Exit Do
            ElseIf CInt(Text1.Text) < myarray(mid) Then  '查找值和当前中间值比较,小了
                high = mid - 1
            Else                                   '查找值和当前中间值比较,大了
                low = mid + 1
            End If
        mid = CInt((high + low) / 2)
        Loop
    End Sub

    Private Sub Form_load()
     Dim i As Integer
        For i = 0 To UBound(myarray)                '给数组赋值
            myarray(i) = i
            Print myarray(i)
        Next i
    End Sub

    学习心得
    1、二分法查找的思想就是:先取中间值作比较,看大了还是小了,大了就往下取数,小了就往上取数。这样逐步缩小查找范围,就不用每个数都去做比较。适用于有序数组,确实能提高计算效率,是一个很不错的思维方式。

    展开全文
  • 二分查找

    2019-03-26 13:43:16
    说在前面的话 略略略略略略啦略啦略啦...二分查找是建立在有序数组上的分治,是比较简单和效率的一种查找算法 和数学上的二分求开方原理一样,都是利用中间值进行折半接近问题的解 代码 public int query(int[] a, i...

    说在前面的话

    略略略略略略啦略啦略啦略啦略略略啦啦啦啦略啦略略略———当你很认真的把这个读出声的时候,你会发现读完之后你会笑一下,然后笑骂了一下博主真傻bi,最后跟着也骂了自己一下,嗯,对,就是这样的

    思想

    二分查找是建立在有序数组上的分治,是比较简单和效率的一种查找算法
    和数学上的二分求开方原理一样,都是利用中间值进行折半接近问题的解

    代码

    public int query(int[] a, int target) {
        int low = 0, high = a.length - 1, middle = 0;
        while (low <= high) {
          middle = (low + high) / 2;
          if (a[middle] > target) {    // target在左半边
            high = middle - 1;
          } else if (a[middle] < target) {   // target在右半边
            low = middle + 1;
          } else {    // 命中,即找到
            break;
          }
        }
        if (a[middle] == target) {
          return middle;
        } else {
          return -1;
        }
      }
    

    例子详解

    给定有序数组=》0 3 4 4 5 5 6 8 9 9,查找数字6,程序执行如下(建议结合代码一起看)
    在这里插入图片描述
    没错,你没看错,这个图就是用电子表格做出来的,就是这么过分。
    然后,大概解释一下这个图:middle = (low + high) / 2是进行折半的公式,
    当a[middle] > target的时候,说明target在左半部分,应该保留左边;
    当a[middle] < target的时候,说明target在右半部分,应该保留右边;
    当a[middle] < target的时候,说明找到指定数值了;
    当最后low > high之后,a[middle] != target,则不命中,反之命中

    时间复杂度

    最好的情况自然是O(1);
    最坏的情况是O(log n),原因如下:
    二分的最坏过程其实就是一棵二叉树一次最深记录的搜索,如下
    在这里插入图片描述
    所以时间复杂度自然就是树高,根据二叉树的基本公式,可以知道:
    树高 = log2(N),所以最坏的情况也就是O(log n)

    空间复杂度

    忽略

    最后

    笔试经常问到一道题:给你。。。这个有序数组,请问需要查询多少次才能定位到目标值。
    这道题把我干蒙了都,因为二分查找代码的实现,high有两种表达方式,一种是[low, high]闭区间,一种是[low, high)开区间,意思就是high可以是等于arr.length,也可以是等于arr.length-1的,理论上这两种方法时间复杂度都是一样的,但是查找长度不一样,那为什么会有上面那种问题呢,是大家都公认使用high=arr.length-1这种编码方式吗?斗胆请教一下各位道友

    这个博主可能有点懒,就写了这么多

    展开全文
  • 一目了然的二分查找

    2016-07-13 16:50:07
    二分查找模板: 能够二分的情况: 1)l,r区间之间单调,一般分为两种: 一:直接二分某一段自然数 二:二分单调数组(如下演示) 如模板所示数组a[] = {0,0,0,1,1,2,3,4,4,4,4,5,8};  共有n = 13个数。  第一种...
  • VB 精典适用源代码

    2021-04-28 01:50:35
    查找方法:按ctrl+f,输入要查找的问题关键字即可每个问题中间用///分隔,这只是一部分最常见到的问题,以后会逐渐更新。////////////////////////////////////////////////////////////////////////////////////...
  • 简单易懂,不忍删章去节,作为引32313133353236313431303231363533e4b893e5b19e31333262373935子:Access数据库与ADODB编程入门即然已经了解了那些数据库中的基本概念,那么我们就只说说在VB中使用数据库编程首先有...
  • vb语言代码大全

    万次阅读 多人点赞 2019-09-25 03:24:17
    VisualBasic是微软公司推出的简单...本文主要介绍的就是vb语言代码大全,分别从五种常用的vb语言代码中来详细说明,跟随小编一起来了解一下吧。 vb语言代码大全 1、数值型函数: abs(num): 返回绝对值 ...
  • 在我们的编程学习中,遇到了一些问题需要将一个大规模的问题分解成几个较小规模的问题,通过对较小规模问题的求解达到对整个问题的解,这种方法叫做分治法,而在分治法中又衍生出来了一个小方法,叫做二分查找,相信...
  • 根据二分法、牛顿迭代法、拉格朗日插值法、雅可比迭代法来进行计算,并进行相应的程序编程。
  • 这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、...
  • VB精典实用源代码(详细))》由会员分享,可在线阅读,更多相关《VB精典实用源代码(详细))(27页珍藏版)》请在人人文库网上搜索。1、个人收藏的VB精典实用源代码。若朋友您想要问如何才能学好vb,或者入门需要看什么...
  • vb编程代码大全

    千次阅读 2017-07-13 09:49:00
    DateDiff(间隔单位,日期一,日期):计算时间差 日期-日期一 Datepart(间隔单位,日期):计算日期的间隔单位值 Dateserial(date):输出日期值(按序列计算) Timeserial(time):输出时间值(按序列计算) Date...
  • 计算机级考试.题库-vb程序题 |编写一个复制字符串的程序,如图所示。界面要求:使用文本框、命令按钮完成。运行要求:、点击“清除”按钮,将所有的文本框内容清空;、点击“复制”按钮,如上面文本框有选中的文本...
  • 图书馆管理系统代码vb.net)

    热门讨论 2009-03-19 21:54:09
    章 研究现状及设计目标 11 2.1 相关系统研究分析 11 2.1.1 系统设计特点: 11 2.1.2 系统的安全性: 11 2.2 设计目标及要求 12 2.2.1 设计目标 12 2.2.1.1 任务概述 12 2.2.1.2 实现目标 12 2.2.1.3 系统特点 13 ...
  • 计算机VB教程

    2021-07-10 00:56:32
    计算机VB教程 (83页) 本资源提供全文预览,点击全文预览即可全文预览,如果喜欢文档就下载吧,查找使用更方便哦!14.90 积分大学计算机基础教程 TaiYuan University of Technology 第2章 VB编程入门 Visual Basic...
  • VB 精典实用源代码

    2011-03-09 10:33:44
    查找方法:按ctrl+f,输入要查找的问题关键字即可每个问题中间用///分隔,这只是一部分最常见到的问题,以后会逐渐更新。////////////////////////////////////////////////////////////////////////////////////...
  • 上海计算机vb模拟题 (6页) 本资源提供全文预览,点击全文预览即可全文预览,如果喜欢文档就下载吧,查找使用更方便哦!19.90 积分一、选择题一、选择题 1.1.下列赋值语句下列赋值语句____________是是 有效的。...
  • p=ABS(X):取X的绝对值. p=Log(X):求X的自然对数. Y=Sgn(X):符号函数. 说明: X>0时Y=1;... 计算机等级考试VB常用函数解析.doc 下载Word文档到电脑,方便收藏和打印[全文共1545字] 编辑推荐: 下载Word文档
  • 甚至在你写完之前,都不要参考其他的二分查找代码。     3.甚至于我不得不强调,别调用bsearch(),或使用其他瞒天过海的手法     4.时间自己来定:5分钟不短——只要你能保证写完写对;8小时...
  • 2016计算机VB上机考试答题攻略计算机等级考试时间将近,下面是百分网小编为同学们搜索整理了关于计算机VB上机考试答题攻略,供参考学习,希望对大家备考有所帮助。想了解更多相关信息请持续关注我们应届毕业...
  • 浅谈全国计算机等级考试级(VB)上机考试备考方略论文关键词:VB 上机考试 备考方略论文摘要:该文针对VB 上机考试的特点,对于如何进行复习,如何使用VB环境以及如何参加上机考试等几个方面阐述了考生备考的方略,...
  • 浙江高考VB之排序系列

    千次阅读 2021-07-28 22:40:58
    这种排序方法, 很巧妙地把二分的思想结合起来.    咋双向开工? 其实就是有两个指针一个负责找最大值,一个负责找最小值, 然后按照一定的排序顺序把找到的最值放在两边. 代码如下: Dim maxIndex As Integer,...
  • 1、姓名:________________ 班级:________________ 学号:________________-密-封 -线- 全国计算机等级考试VB模拟试题11考试时间:120分钟 考试总分:100题号一三四五总分分数遵守考...
  • 原标题:2016年计算机VB上机考试解题技巧常用算法熟练地掌握算法原理、编程思想和代码实现,就能够做到举一反三,轻松备考,顺利过关。试题推荐:1.累加与连乘基本思想:设置初值,循环计算。扩展:(1)计算指定...
  • 在零零年代,我花了8年时间读完了自考计算机应用大专,这个文凭没有半点水分,毕业时没有走后门,没有托关系,所有的课程全部通过,即60以上,在自考的十几门课程中,皆顺利的以一次或两次通过,唯独一门“电子...
  • (1)数据说明顺序应规范化,使数据的属性更易于查找,从而有利于测试、纠错与维护。原则上,数据说明的次序与语法无关,其次序是任意的,但是便于阅读和理解,最好使其规范化,使说明次序按照某种规则固定。例如,...
  • VB复习§1、VB的特点、运行环境、对象、属性、方法、事件各概念,尤其是方法和事件的区分。熟悉VB的IDE,VB开发应用程序的一般步骤。特点:GUI(集成开发环境)、OLE(对象的连接和嵌入)、OOP(面向对象);运行环境:...
  • 全国计算机等级VB考试题型与解题技巧一、上机考点由于上机考试的方式和主要考点没有很大变化,因此可以通过分析历届上机考题来归纳总结上机考试考核的重点,我们下面来介绍近几年级Visual Basic上机考试所考...
  • VB字符串处理大全

    万次阅读 2018-09-16 11:56:53
    1 VBA中的字符串 2 VBA中处理字符串的函数  2.1 比较字符串 ... 2.6 查找字符串  2.7 提取字符/字符串  2.8 删除空格  2.9 返回字符代码  2.10 返回数值代表的相应字符  2.11 使用字节的函数  ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,664
精华内容 3,865
关键字:

vb二分查找代码