查找排序习题讲解.doc

第7章 查找 【例7-1】有序表按关键字排列如下：7，14，18，21，23，29，31，35，38，42，46，49，52，在表中查找关键字为14和22的数据元素，并画出折半查找过程的判定树。 解：折半查找的过程描述如下： ① low=1；high=length； //设置初始区间 ② 当lowhigh时，返回查找失败信息 //表空，查找失败 ③ low≤high，mid=(low+high)/2; //取中点 a. 若kxtbl.elem[mid].key，high=mid-1；转② //查找在左半区进行 b. 若kxtbl.elem[mid].key，low=mid+1；转② //查找在右半区进行 c. 若kx=tbl.elem[mid].key，返回数据元素在表中位置 //查找成功 查找关键字为14的过程如下： 0 1 2 3 4 5 6 7 8　 9 10 11 12 13 7 141821232931353842464952 ↑ 　↑ low=1 ①设置初始区间 high=13 ─────────────────────────── ↑ ②表空测试，非空； mid=7 　③得到中点，比较测试为a情形 ↑ ↑ low=1 　　 high=6 high=mid-1，调整到左半区 ──────────────────────────── ↑ ②表空测试，非空； mid=3 ③得到中点，比较测试为a情形 ↑ ↑ low=1 high=2 high=mid-1，调整到左半区 ──────────────────────────── ↑ ②表空测试，非空； mid=1 ③得到中点，比较测试为b情形 ↑↑ low=2 high=2 low=mid+1，调整到右半区 ──────────────────────────── ↑ ②表空测试，非空； mid=2 ③得到中点，比较测试为c情形 查找成功，返回找到的数据元素位置为2 查找关键字为22的过程如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 141821232931353842464952　　　　　 ↑ ↑ low=1 ①设置初始区间 　　　　 high=13 ──────────────────────────── 　　　　　　 ↑ ②表空测试，非空； 　　　　 mid=7 ③得到中点，比较测试为a情形 　↑ 　　　　 ↑ low=1 　　　 high=6 high=mid-1，调整到左半区 ─────────────────────────── 　　↑ ②表空测试，非空； 　　mid