Puzzle: LgN algorithm for Index == Value(idiomatic-fu.appspot.com)

4 pointsby tim_swvor 17 Jahren9 comments

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.

lsbvor 17 Jahren

This is a binary sort. How is that interesting?

spaghettivor 17 Jahren

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

spaghettivor 17 Jahren

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

shrughesvor 17 Jahren

Typo alert! You meant

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

spaghettivor 17 Jahren

ok corrected. thanks.

bfvor 17 Jahren

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

spaghettivor 17 Jahren

good point. add

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

bfvor 17 Jahren

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