判断下面的二分搜索算法是否正确。 int binarySearch(int a[], const int x, int n) { if(n>0 && x >= a[0]) { int left = 0; int right = n - 1; while(left < right) { int middle = (left + right) / 2; if(x < a[middle]){ right = middle - 1; } else{ left = middle; } } if(x == a[left]) { return left; } } return -1; }
时间: 2024-02-10 12:08:03 浏览: 21
这个二分搜索算法是错误的。
当x >= a[0]且n>0时,进入while循环后,如果x < a[middle],则令right = middle - 1,这是正确的,但是当x >= a[middle]时,令left = middle是错误的,正确的应该是left = middle + 1,因为此时a[middle]已经被排除在候选区之外了,应该从middle + 1开始搜索下一个候选区。
另外,当left == right时,应该退出循环,而不是在循环内部再次比较一次。
改正后的代码如下:
```
int binarySearch(int a[], const int x, int n) {
if(n > 0 && x >= a[0]) {
int left = 0;
int right = n - 1;
while(left <= right) {
int middle = (left + right) / 2;
if(x < a[middle]) {
right = middle - 1;
} else if(x > a[middle]) {
left = middle + 1;
} else {
return middle;
}
}
}
return -1;
}
```