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.

This is a binary sort. How is that interesting?

For those that like these puzzles there's tons at TopCoder.com, spoj.pl, usaco, etc.

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;
			
		}
	}
}

Typo alert! You meant

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

ok corrected. thanks.

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

good point. add

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

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