CS201: Elementary Data Structures

/******************************************************************************
 * File: FibonacciSearch.hh
 * Author: Keith Schwarz (htiek@cs.stanford.edu)
 *
 * An implementation of the Fibonacci search algorithm, an algorithm for
 * locating the position of a particular key in a sorted sequence of elements
 * in logarithmic time.  It is similar to binary search, though it uses a
 * different sequence of probes.
 *
 * The idea behind the algorithm is to do a modified binary search where
 * instead of probing the middle of the range at each step, we probe indices
 * based on the Fibonacci numbers.  In particular, at each point our probe is
 * at the index of the largest Fibonacci number smaller than the size of the
 * entire array.
 *
 * To understand how the search works, it's best to see it graphically.  If we
 * begin with a range of elements, we can split that range into two pieces,
 * one of which has a size equal to the largest Fibonacci number smaller than
 * the array size, and one of which has size equal to the rest of what remains.
 * This is shown here:
 *
 *     +------------------------------------+------------------------+
 *     |            F(k) elements           |   n - F(k) elements    |
 *     +------------------------------------+------------------------+
 *
 * When we probe the F(k)th element and decide which half we should search on,
 * we have two options.  If the element is in the block containing F(k)
 * elements, then we split those F(k) elements into two groups of size F(k-1)
 * and F(k-2), then recursively probe the split point, which occurs at
 * position F(k-1).  If the element is in the block containing n - F(k)
 * elements, then we begin by noting that n - F(k) < F(k-1), since if this
 * weren't true, then we'd have that n < F(k-1) + F(k) = F(k+1), and it would
 * no longer be true that F(k) is the largest Fibonacci number smaller than the
 * size of the input.
 *
 * One subtlety we have to be careful about is that when we split the elements
 * into two groups, one of these groups will not have a size that's a Fibonacci
 * number, and so one of the probes we make may be grossly out of range.  For
 * example, suppose that we're trying to search in an array of size 14.  This
 * would be split into two groups of size 13 and 1.  If the element we were
 * searching for were equal to that last element, the series of probes we would
 * be making would start at position 13 (one-indexed), realize that the element
 * in question is larger than this value, and thus continue at 13 + 5 = 18
 * (one-indexed), which is out of range.  We therefore pretend that the array
 * is padded on the right with infinitely many copies of an infinitely large
 * value, so that any search we make that ends up out of range will always
 * make it look like the element we're searching for is smaller than the value
 * we find.
 *
 * The reason that this algorithm works is due to Zeckendorf's theorem, which
 * states that any number can be written uniquely as the sum of unique
 * Fibonacci numbers in such a way that no two adjacent Fibonacci numbers are
 * used.  This gives rise to the "Fibonacci number system," a way of 
 * representing numbers in a mixed-radix binary system where the kth bit 
 * corresponds to the kth Fibonacci number.  For example, here are the first 
 * few numbers, written out in the Fibonacci number system:
 *
 *     100 = 89 + 8 + 2 + 1   = F(11) + F(5) + F(3) + F(1)
 *                            = 100000101010_F
 *      10 = 8 + 2            = F(5) + F(3)
 *                            = 101000_F
 *     137 = 89 + 34 + 13 + 1 = F(11) + F(9) + F(6) + F(1)
 *                            = 101001000010_F
 *
 * When executing a Fibonacci search, we are trying to recover each of these
 * Fibonacci bits one at a time.  The first probe sees whether the first digit
 * is a one or a zero.  If it's a one, then we know that the next digit must be
 * a zero (because no two consecutive Fibonacci numbers are used), while if
 * it's a zero we check whether the next digit is a one or zero with another
 * probe because we can't immediately tell its value.
 *
 * Fibonacci search is rarely used in practice, because a standard binary
 * search can be much more effective, but it is useful in that it does not do
 * any divisions - all the probes are computed from additions and subtractions.
 * This can be useful in some applications.
 *
 * This code relies on the existence of a FibonacciIterator class, also
 * available from the Archive.  You can find it online at
 *
 *    http://www.keithschwarz.com/interesting/code/?dir=fibonacci-iterator
 */
#ifndef FibonacciSearch_Included
#define FibonacciSearch_Included

/**
 * bool FibonacciSearch(RandomIterator begin, RandomIterator end, 
 *                      const Value& value);
 * Usage: if (FibonacciSearch(v.begin(), v.end(), value)) ...
 * ----------------------------------------------------------------------------
 * Uses the Fibonacci search technique to scan the range [begin, end) for the
 * given value, returning whether or not it was found.
 */
template 
bool FibonacciSearch(RandomIterator begin, RandomIterator end, 
                     const Value& value);

/**
 * bool FibonacciSearch(RandomIterator begin, RandomIterator end, 
 *                      const Value& value, Comparator comp);
 * Usage: if (FibonacciSearch(v.begin(), v.end(), value, myComparator)) ...
 * ----------------------------------------------------------------------------
 * Uses the Fibonacci search technique to scan the range [begin, end) for the
 * given value, returning whether or not it was found.  The elements are
 * assumed to be sorted in ascending order according to comp.
 */
template 
bool FibonacciSearch(RandomIterator begin, RandomIterator end, 
                     const Value& value, Comparator comp);

/* * * * * Implementation Below This Point * * * * */

#include    // For std::distance, std::iterator_traits
#include  // For std::less
#include "FibonacciIterator.hh"

/* Main implementation of Fibonacci search uses a Fibonacci iterator to access
 * the consecutive Fibonacci numbers as efficiently as possible.
 */
template 
bool FibonacciSearch(RandomIterator begin, RandomIterator end, 
                     const Value& value, Comparator comp) {
  /* See what type we use to keep track of iterator distances, then use that
   * to build our Fibonacci iterator.
   */
  typedef typename std::iterator_traits::difference_type Integer;

  /* Create a Fibonacci iterator so that we can quickly access Fibonacci values
   * in sequence.
   */
  FibonacciIterator itr;

  /* Find the smallest Fibonacci number greater than the number of elements in
   * the range, then back it up one step.  This loop always executes at least
   * once, since when the iterator starts off it has value zero, which can't be
   * bigger than the number of elements.  For this reason, we write this as a
   * do ... while loop to make it clearer what's going on.
   */
  do
    ++ itr;
  while (*itr <= end - begin);

  /* Back up a step, which is well-defined because we took at least one
   * step.
   */
  -- itr;

  /* Until the iterator has reached zero (meaning that there's nothing left to
   * check), apply the Fibonacci search to the range.
   */
  while (*itr != Integer(0)) {
    /* See if this element is in range.  If it isn't, then we need to back the
     * iterator up a step.  Note that we allow *itr to be equal to end - begin
     * because we always read right before the given index (see below).
     */
    if (*itr > end - begin) {
      -- itr;
    }
    /* Otherwise, compare the element at the given index to the value we're
     * looking for.  If the current element is larger, then we look in the
     * first half of the array.
     *
     * Notice that we compare the value at begin[*itr - 1] rather than at
     * begin[*itr].  This is because the array is zero-indexed, but *itr is
     * giving us back one-indexed locations.
     */
    else if (comp(value, begin[*itr - Integer(1)])) {
      -- itr;
    }
    /* If the value we're probing is larger than the element in question, then
     * we continue the search on the right.  We also drop the Fibonacci number
     * twice in order to avoid a useless comparison.
     */
    else if (comp(begin[*itr - Integer(1)], value)) {
      begin += *itr;
      -- itr; -- itr;
    }
    /* Otherwise, we know that the values match, and so we're done. */
    else
      return true;
  }

  /* If we made it here, we didn't find the value in question. */
  return false;
}

/* Non-comparator version implemented in terms of the comparator version. */
template 
bool FibonacciSearch(RandomIterator begin, RandomIterator end,
                     const Value& value) {
  return 
    FibonacciSearch(begin, end, value,
                    std::less::value_type>());
}

#endif

Source: Keith Schwarz, http://www.keithschwarz.com/interesting/code/?dir=fibonacci-search
 This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.