五、查找（4 题）

2026 校订版 · 专题阅读 · 保留代码与校订注 · 与版本锁一致

五、查找（4 题）¶

1. 在有序表中二分查找 `key`¶

回源 · PDF 第 25 页 · b_25_0

非递归¶

int binarySearch(SqList L, int key) {
    int low = 0;
    int high = L.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (L.data[mid] == key)
            return mid + 1;  // 返回从 1 开始的逻辑位置
        if (L.data[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }

    return -1;
}

复杂度： 时间 O(log n)，额外空间 O(1)。

回源 · PDF 第 25 页 · b_25_0；PDF 第 25 页 · b_25_3；PDF 第 25 页 · b_25_8

递归¶

int binarySearchRecursive(SqList L, int key, int low, int high) {
    if (low > high)
        return -1;

    int mid = low + (high - low) / 2;
    if (L.data[mid] == key)
        return mid + 1;
    if (L.data[mid] < key)
        return binarySearchRecursive(L, key, mid + 1, high);
    return binarySearchRecursive(L, key, low, mid - 1);
}

复杂度： 时间 O(log n)，递归栈空间 O(log n)。

回源 · PDF 第 25 页 · b_25_1；PDF 第 25 页 · b_25_9

2. 判断链式二叉树是否为二叉搜索树¶

回源 · PDF 第 25 页 · b_25_2

方法一：中序遍历必须严格递增¶

bool isBSTInorderImpl(BiTree root, bool *hasPrevious, int *previous) {
    if (root == NULL)
        return true;

    if (!isBSTInorderImpl(root->lchild, hasPrevious, previous))
        return false;

    if (*hasPrevious && root->data <= *previous)
        return false;
    *previous = root->data;
    *hasPrevious = true;

    return isBSTInorderImpl(root->rchild, hasPrevious, previous);
}

bool isBSTInorder(BiTree root) {
    bool hasPrevious = false;
    int previous = 0;
    return isBSTInorderImpl(root, &hasPrevious, &previous);
}

回源 · PDF 第 25 页 · b_25_2；PDF 第 25 页 · b_25_4；PDF 第 25 页 · b_25_10

方法二：为每个结点维护合法取值区间¶

bool isBSTByRange(BiTree root, long long low, long long high) {
    if (root == NULL)
        return true;

    long long value = root->data;
    if (value <= low || value >= high)
        return false;

    return isBSTByRange(root->lchild, low, value)
        && isBSTByRange(root->rchild, value, high);
}

调用方式：isBSTByRange(root, LLONG_MIN, LLONG_MAX)。

复杂度： 两种方法时间均为 O(n)，递归栈空间均为 O(h)。

核心思路： 第一种方法利用 BST 中序序列严格递增的性质；第二种方法确保每个结点同时满足所有祖先施加的上下界，而不只是与直接双亲比较。

回源 · PDF 第 26 页 · b_26_0；PDF 第 26 页 · b_26_4

3. 判断顺序存储的二叉树是否为二叉搜索树（2022 年统考题）¶

typedef int ElemType;

typedef struct {
    ElemType node[MAXSIZE];
    bool exists[MAXSIZE];
    int storageLength;  // 已使用存储区长度，即最大可能下标 + 1
} SqBiTree;

bool isArrayBST(SqBiTree T, int index,
                long long low, long long high) {
    if (index >= T.storageLength || !T.exists[index])
        return true;

    long long value = T.node[index];
    if (value <= low || value >= high)
        return false;

    return isArrayBST(T, 2 * index + 1, low, value)
        && isArrayBST(T, 2 * index + 2, value, high);
}

调用方式：isArrayBST(T, 0, LLONG_MIN, LLONG_MAX)。

复杂度： 时间最坏 O(n)，递归栈空间 O(h)。

校订注：原稿使用 T.Node[i] == -1 表示空结点，这会与合法关键字 -1 冲突。本版用独立的 exists[] 标记结点是否存在。storageLength 表示有效存储区长度（最大可能下标加 1），不是实际结点数；否则稀疏存储时可能漏掉较大下标处的结点。

回源 · PDF 第 26 页 · b_26_1；PDF 第 26 页 · b_26_6

4. 判断二叉搜索树是否为平衡二叉树¶

下面用 -1 表示子树已经失衡，否则返回子树高度，因此每个结点只访问一次。

int balancedHeight(BiTree root) {
    if (root == NULL)
        return 0;

    int leftHeight = balancedHeight(root->lchild);
    if (leftHeight == -1)
        return -1;

    int rightHeight = balancedHeight(root->rchild);
    if (rightHeight == -1)
        return -1;

    if (abs(leftHeight - rightHeight) > 1)
        return -1;

    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

bool isBalancedBST(BiTree root) {
    return balancedHeight(root) != -1;
}

复杂度： 时间 O(n)，递归栈空间 O(h)。

校订注：原稿对每个结点重复调用 height()，最坏时间复杂度是 O(n²)，不是标注的 O(n)。本版改成一次后序遍历。题设已保证输入为二叉搜索树，因此这里只需验证每个结点的左右子树高度差不超过 1。

回源 · PDF 第 26 页 · b_26_2；PDF 第 26 页 · b_26_8