二分查找法（Binary Search)

二分查找法（Binary Search）是一种高效的查找算法，适用于在有序数组或列表中查找特定元素。它的基本思想是通过不断将搜索范围减半来快速定位目标值。
算法步骤
初始化：设定搜索范围的起始点 left 和结束点 right，初始时 left = 0，right = 数组长度 - 1。

计算中间点：计算中间位置 mid = left + (right - left) // 2。

比较中间值：

如果 arr[mid] == target，找到目标值，返回 mid。

如果 arr[mid] < target，说明目标值在右半部分，更新 left = mid + 1。

如果 arr[mid] > target，说明目标值在左半部分，更新 right = mid - 1。

重复步骤2-3，直到 left > right，此时未找到目标值，返回 -1。

using System;

class BinarySearch
{
    // 二分查找函数
    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; // 目标值在左半部分
            }
        }

        return -1; // 未找到目标值
    }

    // 主函数
    static void Main(string[] args)
    {
        int[] arr = { 1, 3, 5, 7, 9, 11 }; // 有序数组
        int target = 7;

        int result = BinarySearch(arr, target);

        if (result != -1)
        {
            Console.WriteLine($"目标值 {target} 的索引是: {result}");
        }
        else
        {
            Console.WriteLine($"目标值 {target} 未找到");
        }
    }
}

代码说明
BinarySearch 方法：

接受一个有序数组 arr 和目标值 target。

使用 left 和 right 指针来定义搜索范围。

通过计算中间点 mid 来缩小搜索范围。

如果找到目标值，返回其索引；否则返回 -1。

Main 方法：

定义一个有序数组 arr 和目标值 target。

调用 BinarySearch 方法进行查找，并输出结果。

示例输出
目标值 7 的索引是: 3
时间复杂度
O(log n)，其中 n 是数组的长度。每次比较都将搜索范围减半。

适用条件
数组必须是有序的（升序或降序）。

适用于静态数据（没有频繁插入或删除操作）。

变种
如果需要实现更复杂的二分查找（例如查找第一个等于目标值的索引或最后一个等于目标值的索引），可以对代码进行适当修改。例如：

查找第一个等于目标值的索引

public static int FindFirst(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;
    int result = -1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target)
        {
            result = mid; // 记录当前找到的索引
            right = mid - 1; // 继续在左半部分查找
        }
        else if (arr[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }

    return result;
}