试题四(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;
}
【问题1】(4分)简述二分查找算法的前提条件，以及时间复杂度、空间复杂度。
参考答案前提：待查找数组必须有序(递增或递减)，支持随机访问。时间复杂度：O (logn) 空间复杂度：O (1)
解析：二分查找每次缩小一半查找区间;本代码为迭代实现，仅使用常数变量，空间复杂度为常量级。
粤公网安备44010602001432号