折半搜索,也称二分查找算法、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。
a 搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;
b 如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。
c 如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
时间复杂度折半搜索每次把搜索区域减少一半,时间复杂度为。
(n代表集合中元素的个数)空间复杂度
/// <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) / 2;
if (low > high)
return -1;
else
{
if (arr[mid] == key)
return mid;
else if (arr[mid] > key)
return binarysearch(arr, low, mid - 1, key);
else
return binarysearch(arr, mid + 1, high, key);
}
}
实例:
int[] y = new int[] {1,2,3,4,5,6,7,8,9,10,11,12,13 };
int rr = binarysearch(y, 0, y.length - 1, 13);
console.write(rr); //12
如对本文有疑问,
点击进行留言回复!!
相关文章:
-
-
-
C#实现猜数字游戏
本文实例为大家分享了c#实现猜数字游戏具体代码,供大家参考,具体内容如下给定一个0-100的随机数字猜其大小题目样式:电脑产生一个0到100之间的随机数字,并且...
[阅读全文]
-
-
C# 可空类型的具体使用
在项目中我们经常会遇到可为空类型,那么到底什么是可为空类型呢?下面我们将从4个方面为大家剖析。1、可空类型基础知识顾名思义,可空类型指的就是某个对象类型可以为空...
[阅读全文]
-
-
-
C#实现猜数字小游戏
本文实例为大家分享了c#实现猜数字小游戏的具体代码,供大家参考,具体内容如下效果如图:代码:using system;using system.collecti...
[阅读全文]
-
-
C#实现简单俄罗斯方块
最近在看《.net游戏编程入门经典 c#篇》 第一章介绍了如何制作俄罗斯方块,自己试了试按照书上的步骤,可算是完成了。于是写下这篇文章留作纪念。1.类的设计在充...
[阅读全文]
-
网友评论