二叉排序树建立过程_二叉排序树的建立_二叉排序树的建立算法(3)

若K R[mid].key，则查找成功；若K R[mid].key，则说明如果表中存在要找的结点，该结点一定在R[mid] 的前半部，这时可把查找区间缩小到表的前半部，即low的值不变，修改high的值：high mid -1；否则说明如果表中存在要找的结点，该结点一定在R[mid] 的后半部，这时可把查找区间缩小到表的后半部，即修改low的值：low mid +1，high的值不变。将上述计算mid值并进行比较的过程递归地进行下去，直到查找成功或查找失败 low high 时为止。例9.2 设有序表为： 05, 13, 17, 42, 46, 55, 70, 86 ，图9-2 a 给出了查找关键字为55的结点时的折半查找过程；图9-2 b 给出了查找关键字为12的结点时的折半查找过程。从图9-2 a 可以看到，在查找K 55的结点时，第一次的中点mid是4，由于55 42，查找区间缩小到表的后半部，即修改low的值：low mid +1 5，high的值不变。第二次的中点mid是6，这时R[6].key K，所以经过两次比较而查找成功。图9-2 b 查找失败的情况：在查找K 12的结点时，第一次的中点mid也是4，由于12 42，查找区间缩小到表的前半部，即修改high的值：high mid -1 3，low的值不变。

第二次的中点mid是2，由于12 13，仍需修改high的值：high mid -1 1。第三次的中点mid是1，这时查找区间缩小到一个结点上，因12 05，修改low 的值low mid +1 2，这时有low high 2 1 ，说明查找区间已缩为空也没找到相等的结点，故查找失败。存储结构描述和算法如下：NodeType R[MaxSize]; // 有序的查找表存放在R[1..n] 中keyType K; // 欲查找的给定值存放在K中int n； // 表长int low, high, mid;算法开始时，数组R[1..n] 中顺序存放被查找的线性表,，并已按关键字值从小到大排序。变量K中存放要查找的关键字。算法结束时，若查找成功，则返回查找到的结点下标；否则查找失败，返回0值。算法9.2 折半查找 C/C++ 程序：BinSearch R, n, K int BinSearch NodeType R[ ], int n, KeyType K1. [ 初始化 ] int low, mid, high;low ← 1; high ← n low 1; high n;2. [ 查找区间非空则执行循环 ] while low high 循环，当low high时，执行 mid low+ high /2;⑴ mid ← if K R[mid].key⑵ 若 K R[mid].key return mid;则 return mid [ 查找成功返回 ] if K R[mid].key⑶ 若 K R[mid].key high mid-1;则 high ← mid-1 [ 在前半部查找 ] else否则low ← mid+1 [ 在后半部查找 ] low mid+1;3. return 0 [ 查找失败 ] 4. [ 算法结束 ] ▌ return 0; 折半查找过程可用二叉树来描述，即把当前查找区间的中间位置上的结点R[mid] 作为根，左半部R[1..mid-1]和右半部R[mid+1..high] 的结点分别作为根的左子树和右子树，由此得到的二叉树称为描述折半查找的判定树 decision tree 或比较树 comparison tree 。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-26588-3.html