C语言给出在一个递增有序表A中采用二分查找算法查找值为x的元素的递归算法的程序

以下是C语言的递归实现二分查找算法的程序：

int binarySearch(int arr[], int low, int high, int x) {
    if (high >= low) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == x) {
            return mid;
        }
        if (arr[mid] > x) {
            return binarySearch(arr, low, mid - 1, x);
        }
        return binarySearch(arr, mid + 1, high, x);
    }
    return -1;
}

其中，`arr`为有序数组，`low`和`high`分别表示数组的最低和最高下标，`x`为待查找的元素值。程序首先判断`high`是否大于等于`low`，如果是，则计算出中间位置的下标`mid`，然后判断中间位置的元素是否等于`x`，如果是，则返回`mid`。如果中间位置的元素大于`x`，则在数组的左半部分继续查找；否则，在数组的右半部分继续查找。如果`high`小于`low`，则表示查找失败，返回-1。

相关问题

1．给出在一个递增有序表A中采用二分查找算法查找算法查找值为x的元素的递归算法。 （必做题）C语言程序

下面是在一个递增有序表 `A` 中采用二分查找算法查找值为 `x` 的元素的递归算法的 C 语言程序：

#include <stdio.h>

int binary_search(int A[], int left, int right, int x) {
    if (left > right) {
        return -1;
    }
    int mid = (left + right) / 2;
    if (A[mid] == x) {
        return mid;
    } else if (A[mid] < x) {
        return binary_search(A, mid + 1, right, x);
    } else {
        return binary_search(A, left, mid - 1, x);
    }
}

int main() {
    int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n = sizeof(A) / sizeof(A[0]);
    int x = 6;
    int result = binary_search(A, 0, n - 1, x);
    if (result == -1) {
        printf("元素 %d 不在数组中\n", x);
    } else {
        printf("元素 %d 在数组中的下标为 %d\n", x, result);
    }
    return 0;
}

输出结果为：

元素 6 在数组中的下标为 5

二分查找算法是一种在有序数组中查找元素的高效算法，其基本思想是将数组分成两半，每次将要查找的值与数组中间的值比较，如果相等，返回中间值的下标；如果要查找的值比中间值大，则在右半部分继续查找；如果要查找的值比中间值小，则在左半部分继续查找。以此类推，直到找到要查找的值或者确定要查找的值不在数组中为止。

设二叉树以二叉链表形式存放，用类C语言设计非递归算法判断一棵根结点为T的二叉树是否为二叉排序树。

可以采用中序遍历的方法来判断一棵二叉树是否为二叉排序树。中序遍历的结果应该是一个递增的序列，如果不是递增的，则不是二叉排序树。

具体实现如下：

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

// 定义二叉树结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 定义栈结构体
typedef struct Stack {
    TreeNode *node;
    struct Stack *next;
} Stack;

// 创建节点
TreeNode* createNode(int val) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 插入节点
TreeNode* insertNode(TreeNode *node, int val) {
    if (node == NULL) {
        node = createNode(val);
        return node;
    }
    if (node->val > val) {
        node->left = insertNode(node->left, val);
    } else {
        node->right = insertNode(node->right, val);
    }
    return node;
}

// 创建栈
Stack* createStack() {
    Stack *stack = (Stack*)malloc(sizeof(Stack));
    stack->node = NULL;
    stack->next = NULL;
    return stack;
}

// 入栈
void push(Stack *stack, TreeNode *node) {
    Stack *newNode = createStack();
    newNode->node = node;
    newNode->next = stack->next;
    stack->next = newNode;
}

// 出栈
TreeNode* pop(Stack *stack) {
    if (stack->next == NULL) {
        return NULL;
    }
    TreeNode *node = stack->next->node;
    stack->next = stack->next->next;
    return node;
}

// 非递归中序遍历
int isBST(TreeNode *root) {
    if (root == NULL) {
        return 1;
    }
    Stack *stack = createStack();
    TreeNode *node = root;
    int flag = 1;
    int pre = node->val;
    while (node != NULL || stack->next != NULL) {
        while (node != NULL) {
            push(stack, node);
            node = node->left;
        }
        node = pop(stack);
        if (node->val < pre) {
            flag = 0;
            break;
        }
        pre = node->val;
        node = node->right;
    }
    return flag;
}

// 测试代码
int main() {
    // 构建二叉树
    TreeNode *root = createNode(4);
    insertNode(root, 2);
    insertNode(root, 6);
    insertNode(root, 1);
    insertNode(root, 3);
    insertNode(root, 5);
    insertNode(root, 7);
    // 判断是否为二叉排序树
    int flag = isBST(root);
    if (flag) {
        printf("This is a Binary Search Tree.\n");
    } else {
        printf("This is not a Binary Search Tree.\n");
    }
    return 0;
}

这里我们使用了一个栈来保存遍历的节点，用一个变量pre来保存上一个节点的值，从而判断是否递增。这个算法的时间复杂度为O(n)，空间复杂度为O(h)，其中h为树的高度。