Binary Search

binarySearch.hpp

/* Binary Search [License: CC-BY-SA]
 *  - Copyright(C) 2011 Kazh. All Rights Reserved.
 */

#ifndef __INC_BINARYSEARCH
#define __INC_BINARYSEARCH

#include <stddef.h>
#include <iterator>

/** Search the item of the array by Binary Search Algorithm
 * @tparam        iter    Random Access Iterator to access the array to search
 * @tparam        vtype   Type of items in the array to search
 * @param[in,out] begin   Pointer to head of the array to search
 * @param[in,out] end     Pointer to tail of the array to search
 * @param[in]     item    The item to search
 * @return                Pointer to the found item
 * @retval        NULL    The item was not found in the array
 */
template <
  typename iter,
  typename vtype
  >
iter binarySearch (
  iter begin,
  iter end,
  vtype item
  )
{
  size_t dist = std::distance ( begin, end );

  while ( dist > 1 )
  {
    iter middle = begin + dist / 2;

    if ( *middle == item )
    {
      return ( middle );
    }
    else if ( *middle < item )
    {
      begin = middle + 1;
    }
    else /* if ( *middle > item ) */
    {
      end = middle;
    }
    dist = std::distance ( begin, end );
  }

  return ( NULL );
}

/** Search the item of the array by Head Binary Search Algorithm
 * @tparam        iter    Random Access Iterator to access the array to search
 * @tparam        vtype   Type of items in the array to search
 * @param[in,out] begin   Pointer to head of the array to search
 * @param[in,out] end     Pointer to tail of the array to search
 * @param[in]     item    The item to search
 * @return                Pointer to the found item
 * @retval        NULL    The item was not found in the array
 */
template <
  typename iter,
  typename vtype
  >
iter binarySearchH (
  iter begin,
  iter end,
  vtype item
  )
{
  size_t dist = std::distance ( begin, end );

  while ( dist > 1 )
  {
    iter middle = begin + dist / 2 - 1;

    ( *middle < item ? begin : end )
      = middle + 1;
    dist = std::distance ( begin, end );
  }

  return ( *begin == item ? begin : NULL );
}

/** Search the item of the array by Tail Binary Search Algorithm
 * @tparam        iter    Random Access Iterator to access the array to search
 * @tparam        vtype   Type of items in the array to search
 * @param[in,out] begin   Pointer to head of the array to search
 * @param[in,out] end     Pointer to tail of the array to search
 * @param[in]     item    The item to search
 * @return                Pointer to the found item
 * @retval        NULL    The item was not found in the array
 */
template <
  typename iter,
  typename vtype
  >
iter binarySearchT (
  iter begin,
  iter end,
  vtype item
  )
{
  size_t dist = std::distance ( begin, end );

  while ( dist > 1 )
  {
    iter middle = begin + dist / 2;

    ( *middle > item ? end : begin )
      = middle;
    dist = std::distance ( begin, end );
  }

  return ( *begin == item ? begin : NULL );
}

#endif /* __INC_BINARYSEARCH */

660f69
理論が割と不安。コードに何かあれば教えてください。