【例9.1】有序表按关键码排列如下: 7,14,18,21,23,29,31,35,38, 42,46,49,52 在表中查找关键码为14和22的数据元素。 2021年1月21日 数据结构讲义 21
2021年1月21日 数据结构讲义 21 【例9.１】有序表按关键码排列如下： 7，14，18，21，23，29，31，35，38， 42，46，49，52 在表中查找关键码为14和22的数据元素
(1)查找关键码为14的过程 01234567891011213 7141821232931353842464952 ↑ low=1 ①设置初始区间 high=13 ↑②表空测试,非空; mid=7③得到中点,比较测试为a情形 lOW=1 high=6high=mid-1,调整到左半区 2021年1月21日 数据结构讲义 22
2021年1月21日 数据结构讲义 22 ⑴ 查找关键码为14的过程 ↑ ↑ low=1 ①设置初始区间 high=13 ─────────────────────────── ↑ ②表空测试，非空； mid=7 ③得到中点，比较测试为a情形 ↑ ↑ low=1 high=6 high=mid-1，调整到左半区 ─────────────────────────── 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52
012345678910111213 41821232931353842464952 ↑②表空测试,非空 mid=3③得到中点,比较测试为a情形」 oW=1hgh=2high=md1,调整到左半区 ↑②表空测试,非空; mid=1 ③得到中点,比较测试为b情形 loW=2high=2ow=mid+1,调整到右半区 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 23 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 ↑ ②表空测试，非空； mid=3 ③得到中点，比较测试为a情形 ↑ ↑ low=1 high=2 high=mid-1，调整到左半区 ─────────────────────────── ↑ ②表空测试，非空； mid=1 ③得到中点，比较测试为b情形 ↑↑ low=2 high=2 low=mid+1，调整到右半区
01234567|891011213 7|1418|21232931353842464952 ②表空测试,非空; mid=2 ③得到中点,比较测试为c情形 查找成功,返回找到的数据元素位置为2 (2)查找关键码为22的过程 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 24 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 ↑ ②表空测试，非空； mid=2 ③得到中点，比较测试为c情形 查找成功，返回找到的数据元素位置为2 ⑵ 查找关键码为22的过程
012345678910111213 7141821232931353842464952 ↑ lOW= 1 ①设置初始区间 high=13 ↑②表空测试,非空; mid=7③得到中点,比较测试为a情形 low=1 high=6high=md-1,调整到左半区 ②表空测试,非空 mid=3 ③得到中点,比较测试为b情形 loW=4high=6low=md+1,调整到右半区 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 25 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52 ↑ ↑ low=1 ①设置初始区间 high=13 ─────────────────────────── ↑ ②表空测试，非空； mid=7 ③得到中点，比较测试为a情形 ↑ ↑ low=1 high=6 high=mid-1，调整到左半区 ────────────────────────── ↑ ②表空测试，非空； mid=3 ③得到中点，比较测试为b情形 ↑ ↑ low=4 high=6 low=mid+1，调整到右半区 ───────────────────────────