数据结构篇--折半查找【详解】
折半查找也叫做二分查找或者对数查找，是一种在有序数组中查找特定元素的查找算法。
折半查找的算法步骤如下：
- 将目标关键字key与数组中的中间元素比较，若相等则查找成功。
- key大于中间元素，就到数组中大于中间元素的部分进行查找；若key小于中间元素，就到数组中小于中间元素的部分进行查找，如此，每次查找范围都缩小一半。
- 若是查找范围为空，则代表查找失败。
如果不是很理解，我们就举一个例子。
相信看到上面的流程图，你已经对折半查找有了一个初步的了解。
接下来，我们从代码方面彻底理解它的底层逻辑是如何实现的
C语言代码示例
#include<stdio.h>
#define MaxSize 100
int BinarySearch(int array[], int n, int key) {
int low = 0, high = n - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (key = array[mid]) {
return mid;//查找成功
}
else if (key < array[mid]) {
high = mid - 1;//key比mid关键字小，就在左半部分查找
}
else {
low = mid + 1;//key比mid关键字大，就在右半部分查找
}
}
return -1;
}
int main() {
int array[MaxSize] = { 100,1000,8,15,200 };
int n = 5;
int res = BinarySearch(array, n, 8);
printf("查找结果为: %d", res);
return 0;
}
当然，折半查找的过程中可以用二叉树来描述，称为折半查找判定树，本质就是一种特殊的二叉排序树，它的每个节点都是一个有序数组的中位数，左子树是该中位数左边的有序数组，右子树是该中位数右边的有序数组。
这样的安排保证了在查找时，可以通过比较中位数和目标值的大小关系，来确定目标值在哪个子树中，从而减少折半查找的次数，提高查找效率。
在这个折半查找判定树中，某节点所在的层数即是查找该节点的比较次数。
最后这棵树的样子就是
通过对上面这些知识的理解，我们知道一个有n个数据元素的有序数组，可以构造折半查找判定树
从根节点出发，如果相等就比较成功；反而若是比该结点值小，往左子树走，不然就往右走
就像上面说过的，关键字的比较次数是不会超过该判定树的高度的，并且折半查找判定树本质上是一棵平衡二叉树，还有关键的一点若是树高为h，则前h-1层为满二叉树，所以当使用折半查找时，对于有n个元素的查找表，查找一个数据元素的平均时间复杂度为O（log2N）。
原文地址：https://blog.csdn.net/m0_64056556/article/details/142454446
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！