CODEWITHSUNDEEP
binary-search
Shivam Chauhan
Shivam Chauhan

Reputation: 1856

Topcoder Binary search Tutorial

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. This property is what we use when we discard the second half of the search space. It is equivalent to saying that ¬p(x) implies ¬p(y) for all y < x (the symbol ¬ denotes the logical not operator), which is what we use when we discard the first half of the search space.

Please explain this paragraph in simpler and detailed terms.

Upvotes: 0

Views: 400

Answers (1)

Andr&#233; Fratelli
Andr&#233; Fratelli

Reputation: 6068

Consider that p(x) is some property of x. When using binary search this property is usually x being either greater, lesser, or equal than some other value k that you are looking for.

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.

Lets say that x is some value in the middle of the list and you are looking for where k is. Lets also say that p(x) means that k is greater than x. If the list is sorted in ascending order, than all values y to the right of x (y > x) must also be greater than k (the property is transitive), and as such p(y) also holds for all y. This is the basis of binary search. If you are looking for k and some value x is known to be greater than k, than all elements to its right are also greater than k. Notice that this is only true if the list is sorted. Consider the list [a,b,c] and a value k that you are looking for. If it's known that a < b and b < c, if k < b is true, than k < c must also be true.

This property is what we use when we discard the second half of the search space.

This is what the previous conclusion allows you to do. As you know that the property that holds for x also holds for all y (that is, they are not the element you are looking for, because they are greater) than it's safe to discard them, and as such you keep looking for k only on the lower half.

The rest of the paragraph says pretty much the same thing for discarding the lower half.

In short, p(x) is some transitive property that should hold to all values to the right of any given value x (again, because it's transitive). ¬p(x), on the other hand, should hold for all values to the left of x. By being able to conclude that those are not the elements you are looking for, you can conclude that it's safe to discard either half of the list.

Upvotes: 2

Related Questions