Fibonacci Search
Fibonacci search expands on linear search in that the steps are greater than one. The comments in this C++ implementation explains.
/****************************************************************************** * 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.
Last modified: Monday, November 16, 2020, 8:10 PM