前言
二分查找算法是一种在有序数组中查找特定元素的搜索算法。
实现原理
二分查找的实现依赖于以下几个关键步骤:
-
计算查找范围的中间索引。
-
比较中间索引处的值与目标值。
-
根据比较结果调整查找范围(左半部分或右半部分)。
-
重复上述步骤直到找到目标值或查找范围为空。
动图演示
看一看二分查找与顺序查找的动态对比图:
代码实现
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,返回-1return -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
参考文章
-
https://blog.csdn.net/Sunnyside_/article/details/114700193