二分法找出第一个大于等于目标值的索引

二分查找法，也称为折半查找，是一种用于在有序数组中快速找到特定元素位置的有效算法。它的基本思想是将数组分为两部分，然后比较目标值与中间元素的大小，如果目标值大于中间元素，则在右半部分继续搜索；如果小于，则在左半部分搜索。这个过程会一直持续到找到目标值或者确定目标值应该插入的位置，即大于所有左边元素而小于等于所有右边元素的那个位置。

具体步骤如下：
1. 确定数组的起始索引（通常是0）和结束索引（数组长度减一）。
2. 计算中间索引，通常是 (起始索引 + 结束索引) / 2。
3. 比较目标值和中间元素的值。
4. 如果目标值等于中间元素，返回当前的索引作为结果。
5. 若目标值小于中间元素，更新结束索引为中间索引减一，并在左半部分数组中重复步骤2~4。
6. 否则，若目标值大于中间元素，更新起始索引为中间索引加一，并在右半部分数组中重复步骤2~4。
7. 当结束索引小于起始索引时，说明已遍历完整个数组仍未找到目标值，此时返回起始索引，表示需要在该位置之后插入目标值。

相关问题

c#用递归二分法找出升序集合内第一个大于特定数字

在 C# 中，你可以使用递归二分查找算法（也称为折半搜索）来寻找升序数组中的第一个大于给定数字的元素。这个算法假设数组已经是有序的。以下是基本的实现步骤：

public static int BinarySearchFirstGreaterThan(int[] array, int target, int low = 0, int high = null)
{
    // 如果high为null，则设置为数组长度减一
    if (high == null) high = array.Length - 1;

    // 递归终止条件
    if (low > high)
        return -1; // 表示找不到比target大的元素

    // 计算中间索引
    int mid = (low + high) / 2;

    // 检查中间元素是否大于目标
    if (array[mid] > target)
    {
        // 如果是，检查左半部分
        return BinarySearchFirstGreaterThan(array, target, low, mid - 1);
    }
    else
    {
        // 否则，继续在右半部分
        return BinarySearchFirstGreaterThan(array, target, mid + 1, high);
    }
}

要使用这个函数，你需要传入一个已排序的整数数组和你要查找的目标值。函数会返回第一个大于目标的元素的索引，如果没有找到，返回 -1。

示例：

int[] sortedArray = { 1, 3, 4, 6, 8, 9 };
int target = 5;
int resultIndex = BinarySearchFirstGreaterThan(sortedArray, target);
if (resultIndex != -1)
    Console.WriteLine($"第一个大于{target}的元素是{sortedArray[resultIndex]}");
else
    Console.WriteLine("没有找到大于目标的元素");

二分法是先找到序列的中点List[M]，与X进行比较，若相等则返回中点下标；否则，若List[M]>X，则在左边的子系列中查找X；若List[M] 试写出算法的伪码描述，并分析最坏、最好情况下的时间、空间复杂度

二分查找（Binary Search）是一种在有序列表中查找特定元素的搜索算法。以下是算法的伪码描述：

function binarySearch(list, X):
    low = 0
    high = length(list) - 1
    
loop:
    if low > high:
        return -1  # 如果找不到元素，返回-1表示未找到
    mid = (low + high) // 2
    if list[mid] == X:
        return mid  # 找到元素，返回其索引
    else if list[mid] < X:
        low = mid + 1  # 如果目标大于中间元素，更新左边界
    else:
        high = mid - 1  # 目标小于中间元素，更新右边界

return not found  # 返回true或false，表示是否找到

**时间复杂度分析**：
- 最好情况（Best Case）：列表的第一个元素就是目标值，此时只需一次比较就找到了，时间复杂度是O(1)。
- 最坏情况（Worst Case）：列表完全排序且目标值不在列表中，每次都将搜索范围减半，直到找到空区间，总共需要log_2(n)次比较，所以时间复杂度是O(log n)，n是列表长度。

**空间复杂度分析**：
- 空间复杂度是O(1)，因为这个算法只需要常数级别的额外空间用于存储临时变量如`low`、`high`和`mid`，不随输入规模的增长而变化。