Shortcut for chapter specific information

Wednesday, May 11, 2011

Binary Search 1 and 2 (CLRS pseudocode)

Ah.  I just wrote my first two binary searches in pseudocode.  Both of them are semantically incorrect.   So it is unlikely that they are right.

So let me write down what I did and explain why they are semantically incorrect.  Since my iterative version and recursive version basically derive from the same concept.  So I will just use my iterative version as the basis.

In CLRS pseudocode
iterative_binary_search(A,lo,hi,key):
1 while lo != hi
2     mi = floor ( (lo + hi)/2)
3     if A[mi] = key
4         return mi
5     else if A[mi] < key
6         hi = mi
7     else // A[mi] > key
8         lo = mi + 1


I never test it. But I still consider this search to be incorrect.  Here is the reason: 
At line 5 and 6, hi was set to mi .  So in the next iteration the element will be repeatedly considered.   Whereas the idea of binary search suggest ones to think a key is in a certain range [l,u]. And after the test at line 3,5,7, there could be three exclusive possibilities. 

So does this specific version works though? I have no idea.  But I decided to use a version which is semantically correct to start with.    So line 6 should be

6         hi = mi - 1
and logically line 1 should be 
1 while lo <= hi
 

No comments:

Post a Comment