在C#中,二分查找(Binary Search)是一种高效的在有序数组中查找特定元素的算法
确保数组已排序:二分查找只适用于已排序的数组。在进行二分查找之前,请确保数组已按升序或降序排列。
初始化边界:将搜索范围的左边界设置为0,右边界设置为数组长度减1。
循环查找:当左边界小于等于右边界时,执行以下操作:
a. 计算中间位置:mid = (left + right) / 2
。
b. 检查中间元素是否是目标值。如果是,则返回中间位置。
c. 如果中间元素小于目标值,则更新左边界:left = mid + 1
。
d. 如果中间元素大于目标值,则更新右边界:right = mid - 1
。
检查边界情况:如果在循环结束后仍未找到目标值,则返回-1表示未找到。
以下是一个C#实现的示例:
public int BinarySearch(int[] arr, int target)
{
int left = 0;
int right = arr.Length - 1;
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] == target)
{
return mid;
}
else if (arr[mid]< target)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
return -1; // 未找到目标值
}
注意:在计算中间位置时,可能会出现整数溢出的情况。为了避免这种情况,可以使用 mid = left + (right - left) / 2
代替 mid = (left + right) / 2
。
通过处理边界情况,你可以确保二分查找在不同的输入条件下都能正常工作。