3 ms·
bool f(vector<int> v){ /* use 0-based indice*/ int lowerBound = 0; int upperBound = v.size() - 1; while(1){ if(lowerBound == upperBound) return v[lowerB
by spaghetti 18y ago
bool f(vector<int> v){
/* use 0-based indice*/
int lowerBound = 0;
int upperBound = v.size() - 1;
while(1){
if(lowerBound == upperBound) return v[lowerBound] == lowerBound;
int i = lowerBound + (upperBound - lowerBound) / 2;
if(v[i] == i){
return true;
}else if(v[i] < i){
lowerBound = i + 1;
}else if(v[i] > i){
upperBound = i - 1;
}
}
}
- shrughes 18y agoTypo alert! You meant int i = lowerBound + (upperBound - lowerBound) / 2;
- spaghetti 18y agook corrected. thanks.
- bf 18y agoYour function crashes when passed an empty vector. Defensive programming please! :-)
- spaghetti 18y agogood point. add if(v.size() == 0) return false;
- bf 18y agoAnd don't get me started with passing by value! Okay, I'll stop being a dick.