/******************************************************************************
* 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 <typename RandomIterator, typename Value>
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 <typename RandomIterator, typename Value, typename Comparator>
bool FibonacciSearch(RandomIterator begin, RandomIterator end,
const Value& value, Comparator comp);
/* * * * * Implementation Below This Point * * * * */
#include <iterator> // For std::distance, std::iterator_traits
#include <functional> // 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 <typename RandomIterator, typename Value, typename Comparator>
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<RandomIterator>::difference_type Integer;
/* Create a Fibonacci iterator so that we can quickly access Fibonacci values
* in sequence.
*/
FibonacciIterator<Integer> 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 <typename RandomIterator, typename Value>
bool FibonacciSearch(RandomIterator begin, RandomIterator end,
const Value& value) {
return
FibonacciSearch(begin, end, value,
std::less<typename std::iterator_traits<RandomIterator>::value_type>());
}
#endif