C#二分查找算法设计实现
2024-09-24 08:33:51
C#二分查找算法设计实现
1.介绍
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。(记住了前提要求是顺序存储结构,而且要有序排序,所以说对于一个无序的是没法用二分查找的)
2.查找算法过程
举例就一个int类型数组为例 比如int[] intArray;
假设数组中元素是按升序排列,将数组中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
复杂度:O(lg n),n为要查找的元素个数。
3.算法要求
- 必须采用顺序存储结构。
- 必须按关键字大小有序排列。
4.算法实现
这里以C#代码实现
4.1递归方法
/// <summary>
/// 二分查找递归实现
/// </summary>
/// <param name="arr">数组</param>
/// <param name="low">开始索引 0</param>
/// <param name="high">结束索引 </param>
/// <param name="key">要查找的对象</param>
/// <returns>返回索引</returns>
public static int BinarySearch(int[] arr, int low, int high, int key)
{
int mid = (low + high) / ;//中间索引
if (low > high)
return -;
else
{
if (arr[mid] == key)
return mid;
else if (arr[mid] > key)
return BinarySearch(arr, low, mid - , key);
else
return BinarySearch(arr, mid + , high, key);
}
}
4.2While循环实现
/// <summary>
/// 二分查找While循环实现
/// </summary>
/// <param name="nums">数组</param>
/// <param name="low">开始索引</param>
/// <param name="high">结束索引</param>
/// <param name="target">要查找的对象</param>
/// <returns>返回索引</returns>
public static int BinaryWhile(int[] nums, int low, int high, int target)
{
while (low <= high)
{
int middle = (low + high) / ;
if (target == nums[middle])
{
return middle;
}
else if (target > nums[middle])
{
low = middle + ;
}
else if (target < nums[middle])
{
high = middle - ;
}
}
return -;
}
5.测试代码
static void Main(string[] args)
{
int[] intArray = new int[] { ,,,,,,,,,};
int result = BinarySearch(intArray,,intArray.Length-,);
Console.WriteLine(result.ToString());
Console.WriteLine("-------------------------------------------");
int resuleWhile = BinaryWhile(intArray,,intArray.Length-,);
Console.WriteLine(resuleWhile.ToString());
Console.Read();
}
6.输出结果
7.源代码工程下载
源码工程项目文件下载
最新文章
- 【英语魔法俱乐部——读书笔记】 1 初级句型-简单句(Simple Sentences)
- Android 学习 (一)
- String,Date,XMLGregorianCalendar的转换
- SQL 金额千分位显示
- long long 读数scanf的转换 #define
- Dubbo 服务暴露注册流程
- zedboard如何从PL端控制DDR读写(二)——AXI总线
- 51nod 数数字(水题)
- unity 双面shader
- 深入理解Java虚拟机读书笔记6----早期(编译期)优化
- Navicat Premium 12.0.29 / 12.1.5.0安装与激活
- Python中的实例方法、classmethod和staticmethod的区别
- Effective Java 第三版——74. 文档化每个方法抛出的所有异常
- php多种方式获得文件扩展名
- Others-阿里专家强琦:流式计算的系统设计和实现
- Gunicorn+Flask中重复启动后台线程问题
- HTTP请求响应码
- asp.net MVC提高开发速度(创建项目模板)
- JS闭包、作用域链、垃圾回收、内存泄露相关知识小结
- Linux-学习笔记(PHP向)<;一>;