C语言二分查找的应用 基本要求： （1）随机生成一个整数序列。 （2）利用该序列构建一棵二叉排序树。 （3）生成一个有序序列。 （4）实现二分查找算法，分析查找的时间复杂度。

C语言中的二分查找通常用于已经排好序的数据结构，如数组或动态构建的二叉搜索树中。以下是这个过程的一般步骤：

1. **生成一个整数序列**：
首先，你需要创建一个大小固定的数组或动态内存，然后通过随机函数生成一组整数并按照升序排列。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void generate_sorted_array(int arr[], int size) {
    srand(time(NULL));
    for (int i = 0; i < size; ++i) {
        arr[i] = rand() % size;
    }
    // 再对数组进行一次排序，例如用快速排序
    qsort(arr, size, sizeof(int), compare_ints);
}

2. **构建二叉搜索树**：
使用二叉插入法将生成的数组元素构建成一棵二叉搜索树。每个节点的左孩子小于父节点值，右孩子大于父节点值。

struct Node {
    int key;
    struct Node *left, *right;
};

struct Node* insert(struct Node* root, int key) {
    // 插入操作...
}

3. **生成有序序列**：
这一步已完成，因为你已经创建了一个有序数组。

4. **实现二分查找算法**：
二分查找算法的核心思想是每次比较中间元素，如果目标值小于中间元素，则在左半部分继续查找；反之，在右半部分查找。直到找到目标值或者范围为空。

int binary_search(int arr[], int low, int high, int target) {
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target)
            return mid;
        else if (arr[mid] < target)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return -1; // 没有找到目标值
}

5. **时间复杂度分析**：
二分查找的时间复杂度是 O(log n)，其中 n 是数据集的大小。这是因为每一次查找都将搜索范围减半，所以对于大规模数据来说效率极高。