试题四(15分，算法设计)
阅读下列说明和 C 代码，回答问题 1 至问题 3。
【说明】采用二分查找算法，在有序递增数组 arr 中查找目标 key。若找到返回对应数组下标;未找到返回 - 1。
int BinarySearch(int arr[],int n,int key){
int low=0,high=n-1;
while(low key){
high = mid -1;
}else{
low = mid +1;
}
}
return -1;
}
【问题3】(6分)二分查找适用于链表存储的有序序列吗?说明理由。
参考答案不适用。链表不支持随机访问，无法直接通过下标获取 mid 位置元素，需要从头遍历寻找中间节点，无法实现二分查找的区间快速定位。
解析：二分查找依赖 O (1) 随机读取元素，链表访问节点需要顺序遍历，失去二分查找效率优势。
粤公网安备44010602001432号