binary1.cpp

来自「数据结构与程序设计教材源码 数据结构与程序设计教材源码」· C++ 代码 · 共 37 行

 
Error_code binary_search_1 (const Ordered_list &the_list,
                            const Key &target, int &position)
/* 
 
Post: If a Record in the_list  has Key equal
      to target, then position locates
      one such entry and a code of success is returned.
      Otherwise, not_present is returned and position is
      undefined.
Uses: Methods for classes
List and Record. 
 
*/

{
   Record data;
   int bottom = 0, top = the_list.size() - 1;

   while (bottom < top) {
      int mid = (bottom + top) / 2;
      the_list.retrieve(mid, data);
      if (data < target)
         bottom = mid + 1;
      else
         top = mid;
   }

   if (top < bottom) return not_present;
   else {
      position = bottom;
      the_list.retrieve(bottom, data);
      if (data == target) return success;
      else return not_present;
   }
}