二分查找法是一种在有序数组中查找特定元素的算法。为了理解它的工作原理，我们需要知道数组是有序的，也就是说，数组中的元素按照升序或降序排列。
二分查找法的基本步骤如下：
-
选择数组的中间元素。
-
如果中间元素正好是目标值，则搜索结束。
-
如果目标值大于中间元素，则只需在数组的右半部分中查找。
-
如果目标值小于中间元素，则只需在数组的左半部分中查找。
-
重复以上步骤，直到找到目标值或者确定目标值不在数组中。
因为每次搜索都会将搜索范围减半，所以算法非常快速和高效。
/// <summary>
/// 二分查找法（折半查找）
/// </summary>
public static void BinarySearchRecursionMain()
{
int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 };
int length = array.Length;
int searchVal = 15;
int result = BinarySearchByRecursion(array, 0, length - 1, searchVal);
if (result == -1)
Console.WriteLine("Element not present in array");
else
Console.WriteLine("Element found at index " + result);
}
/// <summary>
/// 二分查找法(递归实现)
/// </summary>
/// <param name="array">数组</param>
/// <param name="firstIndex">查找范围的开始</param>
/// <param name="length">查找范围的长度</param>
/// <param name="target">查找目标</param>
/// <returns></returns>
public static int BinarySearchByRecursion(int[] array, int firstIndex, int length, int target)
{
//判断是否超过检索范围
if (firstIndex > length)
return -1;
//获取中间索引
int midIndex = firstIndex + (length - firstIndex) / 2;
//中间索引的值
int midVal = array[midIndex];
if (midVal > target) //中间索引值大于目标值则在左半边继续进行二分法查询
return BinarySearchByRecursion(array, firstIndex, midIndex - 1, target);
else if (midVal < target) //目标值大于中间索引值则在右半边继续进行二分法查询
return BinarySearchByRecursion(array, midIndex + 1, length, target);
else //进行对比，值一致则返回
return midIndex;
}
在这个示例中，我们传入一个有序数组arr和一个目标值target。我们使用两个指针firstIndex和length来跟踪搜索范围。在每次循环中，我们计算中间元素的索引midIndex