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]