CODEWITHSUNDEEP
binary-search
Aira Banazadeh
Aira Banazadeh

Reputation: 35

Discrete Binary Search Main Theory

I have read this: https://www.topcoder.com/community/competitive-programming/tutorials/binary-search. I can't understand some parts==>

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.

But I think this condition does not hold when we want to find an element(checking for equality only) in an array and this condition only holds when we're trying to find Inequality for example when we're searching for an element greater or equal to our target value.

Example: We are finding 5 in this array.

indexes=0 1 2 3 4 5 6 7 8
        1 3 4 4 5 6 7 8 9

we define p(x)=>

 if(a[x]==5) return true else return false

step one=>middle index = 8+1/2 = 9/2 = 4 ==> a[4]=5 and p(x) is correct for this and from the main theory, the result is that p(x+1) ........ p(n) is true but its not.

So what is the problem?

Upvotes: 2

Views: 223

Answers (1)

sp2danny
sp2danny

Reputation: 7644

We CAN use that theorem when looking for an exact value, because we
only use it when discarding one half. If we are looking for say 5,
and we find say 6 in the middle, the we can discard the upper half,
because we now know (due to the theorem) that all items in there are > 5

Also notice, that if we have a sorted sequence, and want to find any element
that satisfies an inequality, looking at the end elements is enough.

Upvotes: 1

Related Questions