前言
二分查找算法是一种在有序数组中查找特定元素的搜索算法。
实现原理
二分查找的实现依赖于以下几个关键步骤：
- 计算查找范围的中间索引。
- 比较中间索引处的值与目标值。
- 根据比较结果调整查找范围（左半部分或右半部分）。
- 重复上述步骤直到找到目标值或查找范围为空。
动图演示
看一看二分查找与顺序查找的动态对比图：
代码实现
public class 二分查找算法
{
/// <summary>
/// 二分查找算法
/// </summary>
/// <param name="arr">arr是已排序的数组</param>
/// <param name="target">target是要查找的目标值</param>
/// <returns>目标值在数组中的索引，如果未找到则返回-1</returns>
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; // 查找成功，返回索引
}
else if (arr[mid] < target)
{
// 如果目标值小于中间元素，则在左半部分查找
left = mid + 1;
}
else
{
// 如果目标值大于中间元素，则在右半部分查找
right = mid - 1;
}
}
// 未找到 target，返回-1
return -1;
}
public static void BinarySearchRun()
{
int[] arr = { 1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59 }; //注意：这里的数组是已排序的数组
int target = 31; //需要要查找的目标值
int result = BinarySearch(arr, target); //调用二分查找方法
if (result == -1)
{
Console.WriteLine("元素未找到");
}
else
{
Console.WriteLine($"元素找到，索引为：{result}，值为：{arr[result]}");
}
}
}
数据结构与算法实战入门指南
https://mp.weixin.qq.com/s/XPRmwWmoZa4zq29Kx-u4HA