已知一个有7个数据元素的有序顺序表，其关键字为{3,18,25,37,69,87,99}。给出用折半查找方法查找关键字值18的查找过程。

折半查找，也叫二分查找，是一种针对有序顺序表的查找算法。

在本题中，有序顺序表的关键字为{3,18,25,37,69,87,99}，要查找的关键字为18。下面是查找过程：

1. 将查找区间的左右端点分别设为low和high，初始时low=0，high=6（表的下标从0开始）。

2. 计算中间位置mid=（low+high）/2=（0+6）/2=3。

3. 比较关键字18与表中第mid个元素的关键字25，由于18小于25，所以18可能在表的左半部分，将high赋值为mid-1=2。

4. 计算新的中间位置mid=（low+high）/2=（0+2）/2=1。

5. 比较关键字18与表中第mid个元素的关键字18，由于相等，查找成功，返回1。

由此可见，折半查找算法查找关键字18的过程为：low=0, high=6, mid=3; low=0, high=2, mid=1; 找到了关键字为18的元素，返回下标1。

相关问题

1)已知一个有7个数据元素的有序顺序表,其关键字为|3,18,25,37,69,7. 91,请给出用折半查找方法查找关键字值18的查找过程。 2) 已知关键字序列为(53,17,19,61,98,75,79,63,46,40},请给出利用这些关键字构造的二又排序树。

1) 折半查找方法的基本思想是：在有序表中，先取中间位置的记录进行比较，如果给定值与中间位置的记录相等，则查找成功；否则利用中间位置将有序表分成两个子表，若中间位置的记录大于给定值，则在左半部分继续查找；否则在右半部分继续查找。重复以上过程，直到查找成功或查找失败为止。

按照折半查找方法查找关键字值18的过程如下：
1. 设置左右两个哨兵left和right，初始时left=1，right=7；
2. 取中间位置mid=(left+right)/2=4，即中间位置记录的关键字为37；
3. 给定值18小于中间位置记录的关键字37，因此在左半部分继续查找，将right=mid-1=3；
4. 取新的中间位置mid=(left+right)/2=2，即中间位置记录的关键字为18；
5. 查找成功，返回位置2。

因此，关键字值18的查找过程是：37 -> 18，查找成功，返回位置2。

2) 利用这些关键字构造的二叉排序树如下：

53
/ \
17 61
\ \
19 98
/ \
75 79
\
63
/
46
/
40