Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
problem with theorem. | Reply
In the tutorial it says:

What we can call the main theorem states that binary search can be used if and only if for all x in S, p(x) implies p(y) for all y > x.

But that simply isn't correct. Imagine we have a set S = {3,4,5,6}. And, say, we're looking for a number 5. So for 3, 4, 5 would be > then them, for 5 it would be equals, for 6 it would be 5 < 6. So if our predicate is X > A[i], then it'll hold for i = [0,1], and won't hold for the others.

Also I don't get, why use obscure latter solution, when the first one is much more clear to understand. I.e. the one where we're doing (if A[i] == X else if A[i] < X else something else).