程序员经验分享-hwhale

算法 - 折半查找（C#）

2023-11-06
  • 递归实现：

[csharp]  view plain  copy  print ?
  1. // --------------------------------------------------------------------------------------------------------------------  
  2. // <copyright company="Chimomo's Company" file="Program.cs">  
  3. // Respect the work.  
  4. // </copyright>  
  5. // <summary>  
  6. // The binary search (recursive).  
  7. // [折半查找的前提]：  
  8. // 1、待查找序列必须采用顺序存储结构。  
  9. // 2、待查找序列必须是按关键字大小有序排列。  
  10. // </summary>  
  11. // --------------------------------------------------------------------------------------------------------------------  
  12.   
  13. namespace CSharpLearning  
  14. {  
  15.     using System;  
  16.   
  17.     /// <summary>  
  18.     /// The program.  
  19.     /// </summary>  
  20.     internal class Program  
  21.     {  
  22.         /// <summary>  
  23.         /// Entry point into console application.  
  24.         /// </summary>  
  25.         public static void Main()  
  26.         {  
  27.             int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };  
  28.             Console.WriteLine(BinarySearch(a, 6, 0, 9));  
  29.         }  
  30.   
  31.         /// <summary>  
  32.         /// 在下界为low，上界为high的有序数组a中折半查找数据元素x（递归查找）。  
  33.         /// </summary>  
  34.         /// <param name="a">  
  35.         /// 待查找数组。  
  36.         /// </param>  
  37.         /// <param name="x">  
  38.         /// 目标元素。  
  39.         /// </param>  
  40.         /// <param name="low">  
  41.         /// 数组元素下标的下界。  
  42.         /// </param>  
  43.         /// <param name="high">  
  44.         /// 数组元素下标的上界。  
  45.         /// </param>  
  46.         /// <returns>  
  47.         /// 若查找到目标元素则返回该目标元素在数组中的下标；否则返回-1。  
  48.         /// </returns>  
  49.         private static int BinarySearch(int[] a, int x, int low, int high)  
  50.         {  
  51.             if (low > high)  
  52.             {  
  53.                 return -1;  
  54.             }  
  55.   
  56.             int mid = (low + high) / 2;  
  57.             if (x == a[mid])  
  58.             {  
  59.                 return mid;  
  60.             }  
  61.   
  62.             return x < a[mid] ? BinarySearch(a, x, low, mid - 1) : BinarySearch(a, x, mid + 1, high);  
  63.         }  
  64.     }  
  65. }  
  66.   
  67. // Output:  
  68. /* 
  69. 5 
  70. */  
时间复杂度：O(log2n)

  • 非递归实现：

[csharp]  view plain  copy  print ?
  1. // --------------------------------------------------------------------------------------------------------------------  
  2. // <copyright company="Chimomo's Company" file="Program.cs">  
  3. // Respect the work.  
  4. // </copyright>  
  5. // <summary>  
  6. // The binary search (not recursive).  
  7. // [折半查找的前提]：  
  8. // 1、待查找序列必须采用顺序存储结构。  
  9. // 2、待查找序列必须是按关键字大小有序排列。  
  10. // </summary>  
  11. // --------------------------------------------------------------------------------------------------------------------  
  12.   
  13. namespace CSharpLearning  
  14. {  
  15.     using System;  
  16.   
  17.     /// <summary>  
  18.     /// The program.  
  19.     /// </summary>  
  20.     internal class Program  
  21.     {  
  22.         /// <summary>  
  23.         /// Entry point into console application.  
  24.         /// </summary>  
  25.         public static void Main()  
  26.         {  
  27.             int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };  
  28.             Console.WriteLine(BinarySearch(a, 6, 9));  
  29.         }  
  30.   
  31.         /// <summary>  
  32.         /// 在长度为n的有序数组a中查找值为key的元素（非递归查找）。  
  33.         /// </summary>  
  34.         /// <param name="a">  
  35.         /// 待查找数组。  
  36.         /// </param>  
  37.         /// <param name="key">  
  38.         /// 目标元素。  
  39.         /// </param>  
  40.         /// <param name="n">  
  41.         /// 数组长度。  
  42.         /// </param>  
  43.         /// <returns>  
  44.         /// 若查找到目标元素则返回该目标元素在数组中的下标；否则返回-1。  
  45.         /// </returns>  
  46.         private static int BinarySearch(int[] a, int key, int n)  
  47.         {  
  48.             int low = 0;  
  49.             int high = n - 1;  
  50.             while (low <= high)  
  51.             {  
  52.                 int mid = (low + high) / 2;  
  53.                 if (a[mid] == key)  
  54.                 {  
  55.                     return mid;  
  56.                 }  
  57.   
  58.                 if (a[mid] < key)  
  59.                 {  
  60.                     low = mid + 1;  
  61.                 }  
  62.                 else  
  63.                 {  
  64.                     high = mid - 1;  
  65.                 }  
  66.             }  
  67.   
  68.             return -1;  
  69.         }  
  70.     }  
  71. }  
  72.   
  73. // Output:  
  74. /* 
  75. 5 
  76. */  

时间复杂度：O(log2n)

转自：http://blog.csdn.net/troubleshooter/article/details/4621272

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

算法

递归

折半查找

算法 - 折半查找（C#） 的相关文章

  • Dapper 强类型查询返回默认对象值

    刚刚开始使用 Dapper 并喜欢它 我遇到了问题 它返回正确数量的对象 但它们的属性都有默认值 using var dbConnection Connection await dbConnection OpenAsync const st

  • 以编程方式 Godaddy 发送的电子邮件不在“已发送邮件”文件夹中 C#.net

    我正在通过以下方式发送电子邮件ASP NET代码使用godaddy邮件服务器 邮件发送成功 但未存储在已发送邮件文件夹中 我正在使用下面的代码 SmtpClient client new SmtpClient client Host smt

  • boost::interprocess 准备好迎接黄金时间了吗？ [关闭]

    很难说出这里问的是什么 这个问题是含糊的 模糊的 不完整的 过于宽泛的或修辞性的 无法以目前的形式得到合理的回答 如需帮助澄清此问题以便重新打开 访问帮助中心 help reopen questions 我正在开发一个由内存映射文件支持的线

  • C#9 顶级语句文件上的属性

    我正在尝试向顶级语句文件添加属性 但没有找到任何相关信息 是否可以 对于某些上下文 我想仅在该文件中禁用规则 SuppressMessage StyleCop CSharp LayoutRules SA1516 ElementsMustBe

  • C++ - 模板专业化和部分专业化

    我一直在互联网和 stackoverflow 上寻找具体的答案 但我似乎找不到 我必须创建一个通用类 然后实现特定的功能 我的具体说明是 您需要使用模板表达式参数以及模板类专业化和部分专业化 我有一个模板类 template

  • C++：获取注册表值仅给出第一个字符[重复]

    这个问题在这里已经有答案了 我试图从注册表中获取字符串值 但我只得到第一个字母 HKEY hKey char gamePath MAX PATH if RegOpenKeyEx HKEY CURRENT USER L Software Bl

  • C# ConfigurationManager 从 app.config 检索错误的连接字符串

    我有一个简单的 WinForms 应用程序 它最终将成为一个游戏 现在 我正在研究它的数据访问层 但遇到了障碍 我创建了一个单独的项目 名为DataAccess在其中 我创建了一个本地 mdfSQL Server 数据库文件 我还创建了一个

  • 禁用除滚动之外的 DataGridView

    我如何配置 datagridview 以便用户只能在行中移动并使用滚动 而没有其他 如果我禁用网格不允许我使用滚动 将您的 datagridview 设置为只读 这将禁用任何编辑 dataGridView1 ReadOnly true 在你

  • TestMethod：异步任务 TestSth() 不适用于 .NET 4.0

    我正在尝试使用 NET 4 0 BCL Async 和 MsTest 运行异步测试方法 看来这个设置不能处理 测试方法 异步Task测试Sth 由于测试用例资源管理器中缺少条目 将签名更改为异步后void 我可以运行测试用例 但结果错误 根

  • 将占位符文本添加到文本框

    我正在寻找一种将占位符文本添加到文本框的方法 就像在 html5 中使用文本框一样 IE 如果文本框没有文本 则会添加文本Enter some text here 当用户单击它时 占位符文本消失并允许用户输入自己的文本 如果文本框失去焦点并

  • C++ 模板参数类型推断

    我有一个这样的C 模板 template

  • 首先EntityFramework数据库 - 类型映射 - 将binary(8)从SQL映射到C#中的int

    在 SQL 内部 我有一个主键为二进制 8 的表 当我使用该表添加到我的模型中时Update Model from Database我可以看到该列有 type Binary 在 C 中 我将该列设为byte 我可以将该列映射到 int 吗

  • 使用 Microsoft Graph 创建用户

    如何使用 Microsoft graph 创建用户 因为我在保存过程中遇到了权限失败的问题 我确实有几个问题 在图中调用创建用户 API 将在哪里创建用户 是在 Azure AD 还是其他地方 我尝试通过传递 json 和必需的标头来调用创

  • 在 C++ 中处理音频缓冲区时，如何执行从 float -> double -> float 的转换

    我目前正在开发一个应用程序 其中音频样本帧在以下回调中进行处理 void Eav07AudioProcessor processBlock AudioSampleBuffer buffer for int channel 0 channel

  • 在非指针变量和类成员上放置 new

    考虑以下示例 include

  • 打破条件变量死锁

    我遇到这样的情况 线程 1 正在等待条件变量 A 该变量应该由线程 2 唤醒 现在线程 2 正在等待条件变量 B 该变量应该由线程 1 唤醒 在我使用的场景中条件变量 我无法避免这样的死锁情况 我检测到循环 死锁 并终止死锁参与者的线程之一

  • fscanf 和 EOF 中的否定扫描集

    我的文件中有一个以逗号分隔的字符串列表 姓名 1 姓名 2 姓名 3 我想跳过所有逗号来阅读这些名字 我写了以下循环 while true if fscanf file my string 1 break 然而 它总是比预期多执行一次 给定

  • C# - 命名空间内的类型声明

    在命名空间内而不是在类中声明类型的可能用途是什么 For ex namespace Test public delegate void Ispossible 这是有效的并且不会产生任何编译错误 但我无法想象为什么我们会以这种方式声明它而不是

  • 使 C# 编译器相信执行将在成员返回后停止

    我认为目前这是不可能的 或者这是否是一个好主意 但这是我刚才正在考虑的事情 我使用 MSTest 对我的 C 项目进行单元测试 在我的一项测试中 我执行以下操作 MyClass instance try instance getValue

  • 计算两个日期之间的工作日数？

    在C 中 如何计算business 或工作日 两个日期之间的天数 我以前曾经遇到过这样的任务 并且我已经找到了解决方案 当可以避免的时候 我会避免列举其间的所有日子 这里就是这种情况 正如我在上面的一个答案中看到的那样 我什至没有提到创建一

随机推荐

  • DM6446的视频前端VPFE驱动之ioctl控制（视频缓存区，CCDC，decoder)解析之一

    本文均属自己阅读源码的点滴总结 转账请注明出处谢谢 欢迎和大家交流 qq 1037701636 email 200803090209 zjut com gzzaigcn2012 gmail com 在这里分析驱动的ioctl的内容时 需要结

  • Feature Pyramid Networks for Object Detection 论文笔记

    论文地址 Feature Pyramid Networks for Object Detection 前言 这篇论文主要使用特征金字塔网络来融合多层特征 改进了CNN特征提取 论文在Fast Faster R CNN上进行了实验 在COCO

  • 本地jar包上传的maven仓库，引用jar包中的pom依赖无法下载

    新项目开发公共组件 上传到公司maven仓库 记一次本地项目打包 上传到公司maven仓库的坑 mvn deploy deploy file DgroupId com test 分组 DartifactId test jar名称 Dvers

  • 【cuda】——cuda，opencv混合编程

    思路来自 https www cnblogs com dwdxdy p 3528711 html 但是其cuda源码是有问题的 没有cmakelists txt 背景 采用cuda gpu交换opencv图像的 r b通道 0 代码 mai

  • 恒生ufx接口转变成CTP接口

    由于当初自己的程序是对接ctp接口 里面大量使用了ctp的东西 但最近又要对接恒生的系统 想着不改整个程序 把ufx接口封装成ctp的接口形式 这样上层的业务逻辑都不用改了 已实现的主要功能 ReqUserLogin ReqOrderIns

  • C++的mutable

    一 介绍 mutable的中文意思是 可变的 易变的 正好与const相反 在C 中 mutable也是为了突破const的限制而设置的 被mutable修饰的变量 将永远处于可变的状态 即使在一个const函数中 二 用法 如果类的成员函

  • Nginx 动态负载均衡

    Nginx 负载均衡 动态实现 1 概览 1 传统配置实现的负载均衡 在加减服务器的时候 会遇到下面的问题 1 配置文件是默认地址 则需要重载配置文件 nginx s reload 加载配置文件流程 1 主进程通知worker进程进行重启

  • 一文了解什么是字节对齐（超详细）

    目录 1 什么是字节对齐 2 空类 3 带虚函数的类 32位机器 64位机器 1 什么是字节对齐 得分点 什么是内存对齐 内存对齐的原因 内存对齐的规则 标准回答 什么是内存对齐 现代计算机中内存空间都是按照 字节 byte 划分的 从理论

  • mnist数据集转换成图片和csv文档

    通常官网提供的mnist数据集都是压缩格式的文档 有时候我们在使用的时候需要将其 1 解压成图片格式存入文件夹 2 或者保存成csv格式的文档 1 保存成图片格式 windows下 coding utf 8 Created on Tue F

  • linux audit审计服务audit.rules策略参数

    audit是linux内核的特性 可以通过内核参数audit 1来启用 etc audit audit rules是audit的规则文件 本文主要讲述如何利用audit来监视系统重要资源 一 监控文件系统行为 依靠文件 目录的权限属性来识别

  • 统计回文

    回文串 是一个正读和反读都一样的字符串 比如 level 或者 noon 等等就是回文串 花花非常喜欢这种拥有对称美的回文串 生日的时候她得到两个礼物分别是字符串A和字符串B 现在她非常好奇有没有办法将字符串B插入字符串A使产生的字符串是一

  • udev使用笔记

    一 什么是udev udev是linux kernel的设备管理器 在最新的内核版本中kernel 3 10中udev已经代替了以前devfs hotplug等功能 意味着它要处理添加 删除硬件时 所有的用户空间行为 实际上为什么我关注这个

  • 华为OD机试 - 称砝码（Java)

    题目描述 现有n种砝码 重量互不相等 分别为 m1 m2 m3 mn 每种砝码对应的数量为 x1 x2 x3 xn 现在要用这些砝码去称物体的重量 放在同一侧 问能称出多少种不同的重量 输入描述 对于每组测试数据 第一行 n 砝码的种数 范

  • Anduino+esp8266_relay继电器 开发智能开关，APP可远程控制

    一 准备工作 1 在网上要购买一块ESP8266 01s带relay继电器的 价格10几元 2 网上购买一个USB转TTL的转接头 我自己用是CH340 价格几元 3 找一个服务器 当然免费的最好 我用的是酱菜创客平台 此平台是给创客提供一

  • 降温的区块链，或许是一个全新开始！

    现如今 区块链的降温正在让跟风与吹捧现出原形 人们开始从庞杂的区块链市场当中找到新的发展方向 区块链开始从简单的打概念 搞论坛 发ICO 逐步转移到了具体应用上 从这个角度来看 当下降温的区块链或许正孕育着一个全新的开始 区块链开始找到数字

  • STAR法则，被这个理由拒绝这么多次，必须搞明白！

    首先 STAR法则是一种常常被HR使用的工具 用来收集与面试者工作相关的具体信息和能力 一个概念 STAR法则 即为Situation Task Action Result的缩写 具体含义是 Situation情境 HR希望你描述一个你遇到

  • chromecast投屏_如何将手机或者ipad投屏到电脑上

    最玩游戏近老想把ipad投屏到电脑上 于是小编了解了一下现在好用的投屏APP 发现了傲软投屏 这是一款能够同时兼容iOS和安卓系统的同屏软件 支持在Windows及Mac上使用 只要您的安卓系统在5 0及以上 支持Chromecast协议

  • 蓝桥杯 算法训练：最小距离（Java）

    题目 数轴上有n个数字 求最近的两个数 即min abs x y 格式 第一行包含一个整数n 接下来一行 表示n整数 样例输入 6 7 3 4 11 9 17 样例输出 1 思路 刚开始打算使用普通的两两数组元素进行比较 但是发现到达第9个

  • 前端H5使用canvas画爱心以及笑脸

    目录 canvas简介 画爱心 效果 画笑脸 效果 结语 canvas简介 canvas是HTML5中推出的新功能 可以在页面上生成一个画布 使用js可以在画布上绘制一些图形 画爱心 画爱心我们需要用到bezierCurveTo方法 可以绘

  • 算法 - 折半查找（C#）

    递归实现 csharp view plain copy print

热门标签