Puzzle: LgN algorithm for Index == Value

http://idiomatic-fu.appspot.com/puzzle/3002/view

by tim_sw • 17 years ago

4 9 17 years ago

idiomatic-fu.appspot.com

dangoldin• 17 years ago

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.

spaghetti4• 17 years 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• 17 years ago

Typo alert! You meant

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

spaghetti4• 17 years ago

ok corrected. thanks.

bf2• 17 years ago

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

spaghetti4• 17 years ago

good point. add

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

bf2• 17 years ago

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

lsb• 17 years ago

This is a binary sort. How is that interesting?

spaghetti4• 17 years ago

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

Puzzle: LgN algorithm for Index == Value

Related Stories