二分搜索概念
二分查找也称折半查找(Binary Search)它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
二分搜索的背景
二分搜索法的概念和思想可以追溯到古代的中国和埃及,
在中国,二分搜索法的原始形式被称为"二分查找",最早出现在公元3世纪的《张邱建算经》中。该算经描述了一种使用二分查找来求解方程的方法。
在埃及,大约在公元1世纪,亚历山大的希罗提米斯(Hero of Alexandria)使用二分法来求解方程和近似计算根号数的值。他的工作被收录在他的著作《机械术》中。
二分搜索应用场景
需要注意的是,二分搜索要求数据集必须是有序的,否则无法正确进行查找。因此,在应用场景中要确保数据的有序性。
二分搜索广泛应用于各种需要查找特定元素的场景,特别是在大规模数据集中进行查找时,可以大幅提高搜索效率。以下是一些常见的应用场景:
-
在有序数组中查找特定元素:由于有序数组的特性,二分搜索可以快速定位目标元素所在的位置。
-
在字典中查找单词:字典通常按照字母顺序排序,可以利用二分搜索来加快查找单词的速度。
-
在数据库索引中进行查找:数据库的索引通常采用有序结构,可以借助二分搜索来快速定位目标数据。
-
在游戏中的查找操作:例如在一副扑克牌中查找某张牌的位置,或在地图中查找某个地点的坐标等。
二分搜索的代码实现
static void Main(string[] args)
{
int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
int target = 12;
int result = BinarySearchDemo.BinarySearch(arr, target);
if (result != -1)
Console.WriteLine("目标值 " + target + " 在数组中的索引位置为 " + result);
else
Console.WriteLine("目标值 " + target + " 不存在于数组中");
Console.ReadLine();
}
public class BinarySearchDemo
{
public static int BinarySearch(int[] arr, int target)
{
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
// 检查目标值是否等于中间值
if (arr[mid] == target)
return mid;
// 如果目标值小于中间值,将右边界缩小为中间值的左边一位
if (arr[mid] > target)
right = mid - 1;
// 如果目标值大于中间值,将左边界扩大为中间值的右边一位
else
left = mid + 1;
}
// 如果无法找到目标值,返回-1
return -1;
}
}
代码输出结果:
代码解析:
我们使用两个指针 left 和 right 来表示搜索范围的左右边界。
在 while 循环中,我们计算中间值 mid,并检查目标值是否等于中间值。如果是,则返回中间值的索引。
如果目标值小于中间值,说明目标值可能在左半边。我们将右边界缩小为中间值的左边一位。
如果目标值大于中间值,说明目标值可能在右半边。我们将左边界扩大为中间值的右边一位。
如果无法找到目标值,即 left > right,则返回-1。
int[] arr = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
C# int / int 会向下取整数,例如 9 / 2 = 4
例如我们找 12,数组的最大值下标是9,第一次,9 / 2 = 4,判断arr [4]为10,明显10<12,说明数据在右半段
接下来,需要用(4+1)+(9-4)/2=7,这样取到了右边的中间数 ,判断 arr [7]为12,程序结束
总结:
二分搜索算法的用途是在一个已排序的集合中高效地查找目标值。与线性搜索相比,二分搜索的时间复杂度为O(log n),其中n是集合的大小。因此,它特别适用于大型数据集或需要频繁搜索的情况。