4 ms·
Puzzle: LgN algorithm for Index == Value
- dangoldin 18y agoGiven 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.
- spaghetti 18y agobool 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 18y agoTypo alert! You meant int i = lowerBound + (upperBound - lowerBound) / 2;
- spaghetti 18y agook corrected. thanks.
- bf 18y agoYour function crashes when passed an empty vector. Defensive programming please! :-)
- spaghetti 18y agogood point. add if(v.size() == 0) return false;
- bf 18y agoAnd don't get me started with passing by value! Okay, I'll stop being a dick.
- lsb 18y agoThis is a binary sort. How is that interesting?
- spaghetti 18y agoFor those that like these puzzles there's tons at TopCoder.com, spoj.pl, usaco, etc.