二分查找与二叉搜索树搜索算法详解

"这篇文档包含了两种搜索算法的实现：一种是二分查找，另一种是二叉搜索树的查找。二分查找适用于有序数组，而二叉搜索树是一种自平衡的二叉树，适用于动态查找操作。" 二分查找算法是一种在有序数组中查找特定元素的有效方法。它的基本思想是将数组分成两半，然后比较目标值与中间元素，根据比较结果决定是在左半部分还是右半部分继续查找。这个过程会递归地重复，直到找到目标值或者搜索范围为空。文档中提供了两种二分查找的实现方式： 1. 非递归实现： ```cpp int BinarySearch(vector<int> v, int value) { if (v.size() <= 0) return -1; int low = 0; int high = v.size() - 1; int mid = 0; while (low <= high) { mid = low + (high - low) / 2; if (v[mid] == value) return mid; else if (v[mid] > value) high = mid - 1; else low = mid + 1; } return -1; } ``` 这个函数首先检查数组的大小，如果为空则返回-1表示未找到。然后设置两个指针low和high分别表示搜索范围的起始和结束。在循环中，计算中间索引mid，根据比较结果调整搜索范围。 2. 递归实现： ```cpp int BinarySearch2(vector<int> v, int value, int low, int high) { if (low > high) return -1; int mid = low + (high - low) / 2; if (v[mid] == value) return mid; else if (v[mid] > value) return BinarySearch2(v, value, low, mid - 1); else return BinarySearch2(v, value, mid + 1, high); } ``` 递归版本的二分查找通过调用自身来实现，每次将问题规模减半，直到找到目标值或搜索范围为空。 二叉搜索树（BST）是一种特殊的二叉树，其中每个节点的左子树只包含小于当前节点值的节点，而右子树包含大于当前节点值的节点。这使得在BST中查找、插入和删除操作的效率很高。文档中的BST查找算法如下： ```cpp Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree& p) { if (!T) { // 查找不成功 p = f; return false; } else if (key == T->data.key) { // 查找成功 p = T; return true; } else if (key < T->data.key) // 在左子树中继续查找 return SearchBST(T->lchild, key, T, p); else return SearchBST(T->rchild, key, T, p); } ``` 这个函数接受一个二叉搜索树的根节点T、目标键值key、父节点引用f以及目标节点引用p。它首先检查当前节点是否为空，如果为空则表示查找失败。如果目标键值与当前节点的键值相等，则查找成功。否则，根据键值与当前节点键值的比较结果，向左子树或右子树递归查找。 总结来说，这两个搜索算法都涉及了查找操作，但它们的应用场景不同。二分查找适用于静态的、已排序的数组，而二叉搜索树则适用于动态的、需要高效查找、插入和删除操作的数据结构。这两种方法在实际编程中都有广泛的应用，特别是在处理大量数据时。