Topics on Binary Search

Binary Search is notorious for its being both strikingly straightforward from a theoretical point of view and comparatively hard and error-prone when it comes to implementation for a specific occasion (It costs you more time than you would have expected and you might face even more issues coding and debugging it than you have ever expected as well if you are not among those few who are quite comfortable with dealing with boundary conditions). Moreover, it's indeed one of the most frequently used algorithms in the entire computing world. Microsoft .NET framework did quite a good job to incorporate this method as part of its array class, but it is still a few steps short of providing a general method to cover all the potential data structures that it might apply to. Apart from .NET, there are heaps of situations where this method is not available. That's why I really wanted to make a note of a few versions of binary search method here for future reference.

Following is the version I wrote in answer to a call on for such implementations from a post on csdn.
The code is written in sort of the programming language ADA, which I think due to its generic nature can be easily transformed to any other languages. It has been roughly tested, however the correctness or the universal applicability is not guaranteed.

-- Find out the location of an item specified as 'e' if it exists 
-- or where it should be inserted if otherwise
-- in the list specified as 'l' of comparable items of type 'element_t'
-- in ASCENDING order 
-- in the range between the index of the first item specified as 'first' (inclusive)
-- and the index of the last item specified as 'last' (exclusive)
-- and return the resultant index as 'index_t' and a boolean value 'found' indicating
-- whether the item exists or not
procedure binarysearch(l : list_t; first, last : index_t; e : element_t;   
                       index : out index_t; found : out boolean) is  
  lo : index_t := first;    -- lowest index
  hi : index_t := last + 1; -- highest index plus one  
  mi : index_t;             -- middle index 
  vm : element_t;           -- item at the middle index
begin  
  while lo < hi loop        -- Note: this can be relaxed to 'lo != hi'
    mi := (lo + hi) / 2;  
    vm := get(l, mi);  
    if e < vm then          -- flip the operator and that below for DESCENDING order
      hi := mi;  
    elsif vm < e then  
      lo := mi + 1;  
    else                    -- vm equals e, the item is found
      index := mi;  
      found := true;  
      return;  
    end if;  
  end loop;  
  index := lo;              -- item not found, the index it should be 
  found := false;           -- inserted at is returned
end;  

Although I'm quite happy with the above implementation, as mentioned the algorithm may have quite a few variants, which would be added down here later on once it comes up and the author finds it interesting and noteworthy.