我已经测试了向量 a = {1,5,8,12,13} 和 x = 23 的代码,它给我发送了一个分段错误,我不明白为什么:
#include <iostream>
#include <cassert>
#include <vector>
#include <cmath>
using std::vector;
int binary_search(const vector<int> &a, int x) {
int left = 0, right = (int)a.size();
if(left>right) return -1;
right = floor((double)(left + right)/2);
if(a[right] == x){
return right;
}
else if(a[right]>x){
vector<int> w(a.begin(), a.begin() + right);
return binary_search(w,x);
}
else{
vector<int> w(a.begin() + right, a.end());
return binary_search(w,x);
}
}
当程序创建的向量 w 的大小为 1 时,它应该进入无限循环,不是吗?
我们可以有索引start
,end
并且可以指向要进行二分查找的子数组,这样我们就不必显式创建子数组。
int binary_search(vector<int> &a, int start, int end, int x) {
if(start > end)
return -1;
int mid = floor((double)(start + end)/2);
if(a[mid] == x){
return mid;
}
else if(a[mid] > x){
return binary_search(a, 0, mid - 1, x);
}
else{
return binary_search(a, mid + 1, end, x);
}
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句