JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions Binary Search tutorial problem with theorem.
 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).
 Forums Tutorial Discussions Binary Search tutorial problem with theorem. Previous Thread  |  Next Thread