Binary search

The binary search algorithm can only be applied if the data are sorted. You can exploit the knowledge that they are sorted to speed up the search.

The idea is analogous to the way people look up an entry in a dictionary or telephone book. You don't start at page 1 and read every entry! Instead, you turn to a page somewhere about where you expect the item to be. If you are lucky you find the item straight away. If not, you know which part of the book will contain the item (if it is there), and repeat the process with just that part of the book.

If you always split the data in half and check the middle item, you halve the number of remaining items to check each time. This is much better than linear search, where each unsuccessful comparison eliminates just one item.

Binary search - Example

Seek the value 123

Algorithm

        bottom := first element
        top    := last element
        while ((top>=bottom) and (not found)) loop
           mid := (top+bottom)/2
           if (list(mid) = item to find) then
              found := true
           elsif (item to find > list(mid)) then
              bottom := mid +1
           else
              top := mid - 1
           end if      
         end loop
         if found = true 
            wanted item is in database
         else
            wanted item is NOT in database
         end if

Code

        type num_array is array (INTEGER range <>) of integer;

        num: num_array(1..10):=(2,6,7,34,76,123,234,567,677,986);

        function search_list(inarray : num_array; tofind : integer)
        return integer 
        is
  
           found : BOOLEAN:=false;          -- found it yet?
           top, bottom, mid : INTEGER;      -- boundaries for search

        begin
           bottom := inarray'FIRST;
           top    := inarray'LAST;

           while ((not found) and (top>=bottom)) loop
              mid := (top+bottom)/2;
              if (tofind = inarray(mid)) then      -- found element
                 found := true;
              elsif (tofind > inarray(mid)) then   -- in top half
                 bottom := mid + 1;
              else                                 -- in bottom half
                 top:= mid -1;
              end if;
           end loop;
        
           if found then
              return mid;                       -- where we found it   
           else 
              return -1;                        -- wasn't there
           end if;                          

        end search_list;