Talk:Fibonacci search technique

Mathematics Start‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

Largely incorrect

Fibonacci search is not faster than binary search, nor is it primarily useful for sorted arrays. It takes log_φ n probes in the worst case, more by a factor of 1.44 than the log₂ n probes used by binary search. Its primary use is in searching unimodal arrays, and it is well-described for that use already in Golden section search. I don't see the point in listing it here as a separate article. —David Eppstein (talk) 16:24, 29 May 2008 (UTC)[reply]

David: I am not qualified to comment on accuracy, but consulting reliable sources, and examining the sources cited in the article, should resolve that. If you do not think that the technique warrants a separate article, then you should be proposing that this article be merged to Golden section search. Merely suggesting it in a Talk page post will not make it happen. Fibonacci search already redirects to Golden section search, so merging this article would just create another redirect. Finell (Talk) 19:54, 29 May 2008 (UTC)[reply]

Today's changes, stating more specific circumstances under which Fibonacci search could be an effective replacement for binary search, allay my concerns, so I have removed the disputed tag. —David Eppstein (talk) 15:29, 9 June 2008 (UTC)[reply]

in step 1 of the algorithm k=m is assigned, but what is m ? —Preceding unsigned comment added by 122.169.85.134 (talk) 14:21, 2 November 2010 (UTC)[reply]

See the first line of the section: n = F_m is the array size. —David Eppstein (talk) 14:47, 2 November 2010 (UTC)[reply]

I wrote the following implementation of a Fibonacci search, for finding the largest non-negative number satisfying some predicate:

def search(test):
    # Standard binary search invariants:
    #   i <= lo then test(i)
    #   i >= hi then not test(i)
    # Extra invariants:
    #   hi - lo = b
    #   a, b = F_{k-1}, F_k
    a, b = 0, 1
    lo, hi = 0, 1
    while test(hi):
        a, b = b, a + b
        hi = b
    while b != 1:
        mi = lo + a
        if test(mi):
            lo = mi
            a, b = 2*a - b, b - a
        else:
            hi = mi
            a, b = b - a, a
    return lo

>>> search(lambda n: n**2 <= 25)
5
>>> search(lambda n: 2**n <= 256)
8

It is useful when you're trying to do binary search over a group, so you can't take averages. If anybody find it more clear than the current descriptions, I can clean it up and add a description to the wiki page. Thomasda (talk) 00:24, 15 June 2014 (UTC)[reply]

Huh?

"Compared to binary search where the sorted array is divided into two arrays which are both examined recursively and recombined, Fibonacci search only examines locations whose addresses have lower dispersion."

(1) The first part reads like a description of binary mergesort. In binary search only one subarray is examined and there is no recombining. (2) If I can teach algorithms for 36 years without knowing what "lower dispersion" means, it probably needs a definition. It is not one of the 21 possibilities listed at dispersion. Knuth (Vol 3, Ed 2) doesn't have it. Anyway, lower than what? And where is a source? McKay (talk) 06:30, 21 October 2016 (UTC)[reply]