分别画出在线性表(a,b,c,d,e,f,g)中进行折半查找关键码e和g的过程。
时间: 2023-10-11 21:13:08 浏览: 75
折半查找,也称二分查找,是一种常见的查找算法,它的基本思想是:将有序表按照中间位置分成两个子表,如果查找的关键码比中间位置上的关键码大,则在后半部分继续查找;否则在前半部分继续查找,直到找到为止。
下面分别画出在线性表(a,b,c,d,e,f,g)中进行折半查找关键码e和g的过程:
1. 查找关键码e的过程:
(1) 初始化,将整个序列作为查找区间。
(2) 中间位置是d,将查找区间缩小为(a,b,c,d)和(f,g)两个子区间。
(3) 中间位置是b,将查找区间缩小为(a,b)和(c,d)两个子区间。
(4) 中间位置是e,查找成功,返回关键码e的位置。
a b c d e f g
| |
d g
| |
b c
|
e
2. 查找关键码g的过程:
(1) 初始化,将整个序列作为查找区间。
(2) 中间位置是d,将查找区间缩小为(a,b,c,d)和(f,g)两个子区间。
(3) 中间位置是f,将查找区间缩小为(f)和(g)两个子区间。
(4) 中间位置是g,查找成功,返回关键码g的位置。
a b c d e f g
| |
f g
|
g
相关问题
画出在线性表 (a,b,c,d ,e,j,g) 中进行折半查找关键码e的过程。
首先,我们需要确定折半查找的起始点和终止点。由于线性表已经是有序的,我们可以将起始点设为 0,将终止点设为线性表的长度减 1。
第一步,确定中间位置。我们可以通过起始点和终止点的下标计算出中间位置的下标:
```
mid = (0 + 6) / 2 = 3
```
第二步,比较中间位置的关键码和待查找关键码 e 的大小。由于中间位置的关键码是 d,小于 e,所以我们可以将起始点更新为 mid + 1,终止点保持不变。
```
start = mid + 1 = 4
end = 6
```
第三步,再次确定中间位置。这一次,我们可以通过起始点和终止点的下标计算出中间位置的下标:
```
mid = (4 + 6) / 2 = 5
```
第四步,比较中间位置的关键码和待查找关键码 e 的大小。由于中间位置的关键码是 j,大于 e,所以我们可以将终止点更新为 mid - 1,起始点保持不变。
```
start = 4
end = mid - 1 = 4
```
第五步,再次确定中间位置。由于起始点和终止点重合了,我们可以停止查找。此时,我们可以发现中间位置的关键码是 e,即我们成功地找到了待查找的关键码。
综上所述,折半查找关键码 e 的过程如下:
```
start = 0, end = 6
mid = (0 + 6) / 2 = 3
start = mid + 1 = 4, end = 6
mid = (4 + 6) / 2 = 5
start = 4, end = mid - 1 = 4
mid = (4 + 4) / 2 = 4
```
因此,查找关键码 e 的过程中,我们依次比较的关键码依次是 d、j、g、e。
9.2② 试分别画出在线性表(a,b,c,d,e,f,g)中进行折半查找 以查关键字等于e, f和g的过程。
首先,折半查找算法需要在有序的线性表中进行查找。给定线性表 `(a,b,c,d,e,f,g)`,我们需要先对其进行排序,使其变为有序的线性表,例如:
```
(a, b, c, d, e, f, g) -> (a, b, c, d, e, f, g) // 已经有序
```
接下来,我们可以按照以下步骤进行折半查找:
1. 确定查找区间的左右端点 `left` 和 `right`,初值分别为线性表的起始位置和终止位置;
2. 计算区间的中间位置 `mid`,即 `mid = (left + right) / 2`;
3. 比较中间位置的关键字与待查找关键字的大小,如果相等,则查找成功,返回该位置;如果中间位置的关键字大于待查找关键字,则在左半区间查找,即将右端点更新为 `mid - 1`;否则,在右半区间查找,即将左端点更新为 `mid + 1`;
4. 重复步骤2和步骤3,直到找到关键字或者区间为空。
下面分别画出在线性表 `(a,b,c,d,e,f,g)` 中进行折半查找以查找关键字等于 `e`, `f` 和 `g` 的过程。
查找 `e`:
```
(a, b, c, d, e, f, g)
↑ // left = 0, right = 6, mid = 3, a[mid] < e
↑ // left = 4, right = 6, mid = 5, a[mid] > e
↑ // left = 4, right = 4, mid = 4, a[mid] == e
```
查找 `f`:
```
(a, b, c, d, e, f, g)
↑ // left = 0, right = 6, mid = 3, a[mid] < f
↑ // left = 4, right = 6, mid = 5, a[mid] == f
```
查找 `g`:
```
(a, b, c, d, e, f, g)
↑ // left = 0, right = 6, mid = 3, a[mid] < g
↑ // left = 6, right = 6, mid = 6, a[mid] == g
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)