题目
可以满分通过的答案:
`
Position BinarySearch(List L, ElementType X){
Position left = 1;
Position right = L->Last;
while(left<=right){
Position center = (left+right)/2;
if(L->Data[center]>X){
right = center-1;
}else if(L->Data[center]<X){
left = center+1;
}else{
return center;
}
}
return NotFound;
}`
期间我发现,若利用递归,处理不当存在超时现象:
`Position search(ElementType arr[], ElementType X, Position left, Position right)
{
if(right == left){
if(arr[right] != X){
return NotFound;
}else{
return right;
}
}
Position center = (left+right)/2;
if(arr[center] > X){
search(arr,X,left,center);
}else if(arr[center] < X){
search(arr,X,center,right);
}else{
return center;
}
}
Position BinarySearch(List L, ElementType X){
return search(L->Data,X,1,L->Last);
}
`
`
Position search(ElementType arr[], ElementType X, Position left, Position right)
{
if(right == left){
if(arr[right] != X){
return NotFound;
}else{
return right;
}
}
Position center = (left+right)/2;
if(arr[center] > X){
search(arr,X,left,center-1);
}else if(arr[center] < X){
search(arr,X,center+1,right);
}else{
return center;
}
}
Position BinarySearch(List L, ElementType X){
return search(L->Data,X,1,L->Last);
}
`
递归改用这样即可不超时:
`
Position search(ElementType arr[], ElementType X, Position left, Position right)
{
if(right<left){
return NotFound;
}
Position center = (left+right)/2;
if(arr[center] > X){
search(arr,X,left,center-1);
}else if(arr[center] < X){
search(arr,X,center+1,right);
}else{
return center;
}
}
Position BinarySearch(List L, ElementType X){
return search(L->Data,X,1,L->Last);
}
`