showing that any algorithm that accesses an array only by comparisons takes sigma(logn) steps

F开发者_StackOverflow中文版or this I think to properly solve it I need to show that sigma(logn) is its lower bound. I know all of the comparisons in my book run in O(nlogn), but im not sure how to form this into a concrete answer.

---

1. I think you've misread the problem: The array you are given is sorted. You are not sorting it. You are accessing it. Let's play a game. I pick a US state and you try to guess it. Every guess I will tell you if my chosen state is alphabetically before or after your guessed state. How many guesses do you need? The problem gives you a great clue with binary search.

2. Add this to your general algorithm toolbox: To show a lower bound is valid (but not necessarily tight), assume there exists an upper bound that is smaller, and do a proof by contradiction. For your problem, this should be doable.