当前位置：首页 > news >正文

C#算法之二分查找

news 2025/11/22 17:47:03

二分查找（Binary Search）算法是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且调整中间位置以继续搜索，直到找到要找的元素，或者搜索范围为空。

下面是C#中实现二分查找算法的一个简单示例：

using System;class Program
{static void Main(string[] args){// 示例数组，注意这里是有序的int[] arr = { 2, 3, 4, 10, 40 };int target = 10;int result = BinarySearch(arr, target);if (result == -1)Console.WriteLine("元素不存在于数组中");elseConsole.WriteLine($"元素在数组中的索引为: {result}");}// 二分查找算法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; // 调整右边界}}// 未找到目标，返回-1return -1;}
}

在这个示例中，BinarySearch函数接收一个有序数组arr和一个目标值target作为参数。它通过迭代的方式，不断将搜索范围减半，直到找到目标值或搜索范围为空。如果找到目标值，则返回其在数组中的索引；如果未找到，则返回-1。

注意，二分查找算法要求数组是有序的。如果数组无序，需要先对其进行排序，然后再使用二分查找算法。

二分查找算法的原理基于分治法的思想，即将一个大的问题分解成小的子问题来解决。在有序数组中查找特定元素时，二分查找通过不断将数组分成两半，来缩小搜索范围，直到找到元素或搜索范围为空。

具体来说，二分查找算法的工作原理如下：

确定搜索范围：初始时，搜索范围是整个数组，即左边界left为数组的起始位置（索引0），右边界right为数组的结束位置（索引arr.Length - 1）。
计算中间位置：在每次迭代中，计算搜索范围的中间位置mid。为了避免整数溢出，通常使用mid = left + (right - left) / 2来计算中间位置，而不是mid = (left + right) / 2。
比较中间元素与目标值：将中间位置mid处的元素arr[mid]与目标值target进行比较。
- 如果arr[mid]正好等于target，则搜索成功，返回mid作为目标值在数组中的索引。
- 如果arr[mid]小于target，则说明目标值在数组的右半部分（因为数组是有序的），因此将左边界left更新为mid + 1，继续在右半部分搜索。
- 如果arr[mid]大于target，则说明目标值在数组的左半部分，因此将右边界right更新为mid - 1，继续在左半部分搜索。
重复迭代：重复步骤2和步骤3，直到找到目标值或搜索范围为空（即left > right）。如果搜索范围为空时仍未找到目标值，则说明目标值不在数组中，返回-1或其他表示未找到的值。