Puzzle: LgN algorithm for Index == Value(idiomatic-fu.appspot.com)
idiomatic-fu.appspot.com
Puzzle: LgN algorithm for Index == Value
http://idiomatic-fu.appspot.com/puzzle/3002/view
3 comments
Given that the list is sorted you can just modify the basic binary search to do what your want. Choose the middle and then compare the index with the value - depending on the relationship look to the left or right and repeat.
bool f(vector<int> v){
/* use 0-based indice*/ int lowerBound = 0; int upperBound = v.size() - 1;
while(1){
/* 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;
}
}
}And don't get me started with passing by value! Okay, I'll stop being a dick.