On: Puzzle: LgN algorithm for Index == Value

[spaghetti]

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 → spaghetti]

Typo alert! You meant

    int i = lowerBound + (upperBound - lowerBound) / 2;

[spaghetti → shrughes]

ok corrected. thanks.

[bf → spaghetti]

Your function crashes when passed an empty vector. Defensive programming please! :-)

[spaghetti → bf]

good point. add

    if(v.size() == 0) return false;

[bf → spaghetti]

And don't get me started with passing by value! Okay, I'll stop being a dick.