Binary Search 3 (CLRS pseudocode)

Think through the issues of BS1 and BS2.  Wrote a new iterative version.  I verified every steps whether key would be in range [l,u].  This seems to me correct this time.



Also finished Ex. 2.3-5.  Need to start to put binary search into my daily practice routine.

Binary Search 4 (C)

Just back record : I found my binary search (BSRCH 3) was flawed.  In the C-version. It is fixed and it looks like,

     1    int binary_search(int a[],int l,int h,int key)
     2    {
     3      while(l<=h){
     4        int m = l + (h-l)/2;
     5        if(key > a[m])
     6          l=m+1;
     7        else if(key==a[m])
     8          return m;
     9        else /* key < a[m] */
    10          h=m-1;
    11      }
    12      return -1;
    13    }

Ah. My merge sort and binary search in C are all wrong......

By Joshua Bloch found in http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

This surprised me.  So apparently my code in merge sort and binary search are wrong then. 

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