C语言编程实现折半查找算法并分析算法的复杂度与稳定性写出完整代码

折半查找算法，也叫二分查找算法，是一种高效的查找算法。它的基本思想是：将有序数组分成两部分，在每次查找时，将待查找的元素与中间位置元素进行比较，如果相等，则查找成功；如果待查找元素小于中间位置元素，则在左边继续查找；如果待查找元素大于中间位置元素，则在右边继续查找。重复以上步骤，直到找到待查找元素或者确定该元素不在数组中。下面是C语言实现的折半查找算法：

#include <stdio.h>

int binarySearch(int arr[], int n, int x) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == x) {
            return mid;
        } else if (arr[mid] < x) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 7;
    int result = binarySearch(arr, n, x);
    if (result == -1) {
        printf("Element is not present in array\n");
    } else {
        printf("Element is present at index %d\n", result);
    }
    return 0;
}

在上面的代码中，我们首先定义了一个binarySearch函数来实现折半查找算法。该函数接受三个参数：一个有序数组arr，数组的长度n，以及待查找的元素x。函数返回该元素在数组中的位置，如果该元素不存在，则返回-1。在函数中，我们使用了两个指针low和high来表示当前查找范围的左右边界。在每次查找时，我们通过计算中间位置mid来确定待查找元素在左边还是右边，然后相应地更新low和high指针，直到找到待查找元素或者确定该元素不存在。

接下来，我们在main函数中定义了一个有序数组arr，并将其长度存储在n中。我们还定义了待查找的元素x，并调用binarySearch函数来查找该元素在数组中的位置。如果该元素不存在，则输出一条提示消息。

折半查找算法的时间复杂度为O(log n)，其中n是数组的长度。这是因为每次查找都将查找范围缩小一半，因此最多需要进行log n次查找。算法的稳定性是非常好的，因为它不会改变数组中元素的相对顺序