用c语言编写程序，实现顺序查找和折半查找算法，并通过实例验证其正确性和效率。并分析并理解不同查找算法的时间复杂度和空间复杂度。

在C语言中，我们可以分别编写顺序查找（线性查找）和折半查找（二分查找）算法。这两个算法主要用于从已排序数组中搜索特定元素。

1. **顺序查找**（线性查找）:

#include <stdio.h>

int sequential_search(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;
    }
    return -1; // 如果目标未找到，返回-1
}

// 示例
int main() {
    int arr[] = {1, 5, 8, 9, 15};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 9;
    int result = sequential_search(arr, n, target);
    if (result != -1)
        printf("元素 %d 的索引是 %d\n", target, result);
    else
        printf("元素 %d 未找到\n", target);
    return 0;
}

时间复杂度：O(n)，因为最坏情况下需要遍历整个数组。
空间复杂度：O(1)，只用到了几个变量。

2. **折半查找**（二分查找）:

#include <stdio.h>
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;
}

// 示例
int main() {
    int sorted_arr[] = {1, 5, 8, 9, 15};
    int n = sizeof(sorted_arr) / sizeof(sorted_arr[0]);
    int target = 9;
    int result = binary_search(sorted_arr, 0, n - 1, target);
    if (result != -1)
        printf("元素 %d 的索引是 %d\n", target, result);
    else
        printf("元素 %d 未找到\n", target);
    return 0;
}

时间复杂度：O(log n)，因为每次都将搜索范围减半。
空间复杂度：O(1)，同样只用了几个变量。