29:
102:
where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two parts that have sizes that are consecutive
Fibonacci numbers. On average, this leads to about 4% more comparisons to be executed, but it has the advantage that
130:
If the elements being searched have non-uniform access memory storage (i. e., the time needed to access a storage location varies depending on the location accessed), the
Fibonacci search may have the advantage over binary search in slightly reducing the average time needed to access a storage
662:
The two variants of the algorithm presented above always divide the current interval into a larger and a smaller subinterval. The original algorithm, however, would divide the new interval into a smaller and a larger subinterval in Step 4. This has the advantage that the new
135:, binary search may lead to more cache misses because the elements that are accessed often tend to gather in only a few cache lines; this is mitigated by splitting the array in parts that do not tend to be powers of two. If the data is stored on a
122:
The
Fibonacci sequence has the property that a number is the sum of its two predecessors. Therefore the sequence can be computed by repeated addition. The ratio of two consecutive numbers approaches the
139:
where seek time depends on the current head position, a tradeoff between longer seek time and more comparisons may lead to a search algorithm that is skewed similarly to
Fibonacci search.
127:, 1.618... Binary search works by dividing the seek area in equal parts (1:1). Fibonacci search can divide it into parts approaching 1:1.618 while using the simpler operations.
107:), division or multiplication, operations that were less common at the time Fibonacci search was first published. Fibonacci search has an average- and worst-case complexity of
103:
one only needs addition and subtraction to calculate the indices of the accessed array elements, while classical binary search needs bit-shift (see
47:
16:
This article is about the programming algorithm. For the technique for finding extremum of a mathematical function, see
65:
736:
Note that the running time analysis is this article is flawed, as pointed out by
Overholt in 1972 (published 1973).
816:
91:
855:
147:
136:
43:
99:
143:
17:
8:
763:
727:
799:
782:
767:
680:
151:
104:
794:
755:
731:
717:
95:
79:
262:
To test whether an item is in the list of ordered numbers, follow these steps:
116:
849:
830:
124:
87:
722:
705:
759:
746:
Overholt, K. J. (1973). "Efficiency of the
Fibonacci search method".
132:
386:
Alternative implementation (from "Sorting and
Searching" by Knuth):
671:
and is more suitable for accelerating searching on magnetic tape.
131:
location. If the machine executing the search has a direct mapped
842:
Implements the above algorithm (not
Ferguson's original one).
656:
two positions back in the
Fibonacci sequence); and return to
599:
one position back in the
Fibonacci sequence); then return to
612:=1, the algorithm terminates unsuccessfully. Otherwise set (
559:=0, the algorithm terminates unsuccessfully. Otherwise set (
281:= 0, stop. There is no match; the item is not in the array.
94:
that narrows down possible locations with the aid of
38:
may be too technical for most readers to understand
150:(1953) to search for the maximum or minimum of a
847:
787:Proceedings of the American Mathematical Society
203:The array of Fibonacci numbers is defined where
699:
697:
695:
431:, the algorithm searches for a given argument
820:. Vol. 3 (Second ed.). p. 418.
361:. Renumber the remaining elements from 1 to
692:
351:, discard the elements from positions 1 to
798:
783:"Sequential minimax search for a maximum"
721:
549:, the algorithm terminates successfully.
66:Learn how and when to remove this message
50:, without removing the technical details.
745:
703:
739:
502:will be consecutive Fibonacci numbers)
848:
780:
310:, discard the elements from positions
813:
48:make it understandable to non-experts
828:
284:Compare the item against element in
22:
410:whose keys are in increasing order
13:
341:If the item is greater than entry
170:, the array of Fibonacci numbers.
14:
867:
800:10.1090/S0002-9939-1953-0055639-3
142:Fibonacci search is derived from
27:
817:The Art of Computer Programming
300:If the item is less than entry
185:is not a Fibonacci number, let
807:
774:
1:
686:
166:be defined as an element in
157:
92:divide and conquer algorithm
7:
704:Ferguson, David E. (1960).
674:
494:(throughout the algorithm,
86:is a method of searching a
10:
872:
297:If the item matches, stop.
192:be the smallest number in
84:Fibonacci search technique
15:
831:"Fibonaccian search in C"
814:Knuth, Donald E. (2003).
748:BIT Numerical Mathematics
710:Communications of the ACM
389:Given a table of records
706:"Fibonaccian searching"
382:, and return to step 2.
181:is the array size. If
723:10.1145/367487.367496
667:is closer to the old
338:and return to step 2.
196:that is greater than
144:Golden section search
18:Golden section search
829:Lourakis, Manolis.
781:Kiefer, J. (1953).
760:10.1007/BF01933527
146:, an algorithm by
856:Search algorithms
681:Search algorithms
152:unimodal function
105:Bitwise operation
96:Fibonacci numbers
76:
75:
68:
863:
841:
839:
837:
822:
821:
811:
805:
804:
802:
778:
772:
771:
743:
737:
735:
725:
701:
381:
337:
322:
258:
248:
238:
231:
154:in an interval.
80:computer science
71:
64:
60:
57:
51:
31:
30:
23:
871:
870:
866:
865:
864:
862:
861:
860:
846:
845:
835:
833:
825:
812:
808:
779:
775:
744:
740:
702:
693:
689:
677:
648:) (which moves
591:) (which moves
547:
532:
517:
493:
479:
465:
448:
429:
423:
416:
408:
401:
394:
372:
370:
360:
350:
328:
320:
311:
309:
293:
255:
250:
246:
240:
233:
229:
223:
213:
204:
190:
179:
160:
72:
61:
55:
52:
44:help improve it
41:
32:
28:
21:
12:
11:
5:
869:
859:
858:
844:
843:
824:
823:
806:
793:(3): 502–506.
773:
738:
690:
688:
685:
684:
683:
676:
673:
545:
530:
515:
488:
474:
461:
443:
427:
424:< ... <
421:
414:
406:
399:
392:
384:
383:
365:
355:
345:
339:
315:
304:
298:
295:
288:
282:
275:
253:
244:
227:
218:
208:
188:
177:
159:
156:
117:Big O notation
98:. Compared to
74:
73:
35:
33:
26:
9:
6:
4:
3:
2:
868:
857:
854:
853:
851:
832:
827:
826:
819:
818:
810:
801:
796:
792:
788:
784:
777:
769:
765:
761:
757:
753:
749:
742:
733:
729:
724:
719:
715:
711:
707:
700:
698:
696:
691:
682:
679:
678:
672:
670:
666:
660:
659:
655:
651:
647:
643:
639:
635:
631:
627:
623:
619:
615:
611:
607:
603:
602:
598:
594:
590:
586:
582:
578:
574:
570:
566:
562:
558:
554:
550:
548:
541:
537:
533:
526:
522:
518:
511:
507:
503:
501:
497:
491:
487:
483:
477:
473:
469:
464:
460:
456:
453:
449:
446:
442:
438:
434:
430:
420:
413:
409:
402:
395:
387:
379:
375:
368:
364:
358:
354:
348:
344:
340:
335:
331:
326:
318:
314:
307:
303:
299:
296:
291:
287:
283:
280:
276:
273:
269:
265:
264:
263:
260:
256:
243:
236:
230:
221:
217:
211:
207:
201:
199:
195:
191:
184:
180:
173:
169:
165:
155:
153:
149:
145:
140:
138:
137:magnetic tape
134:
128:
126:
120:
118:
114:
110:
106:
101:
100:binary search
97:
93:
89:
85:
81:
70:
67:
59:
49:
45:
39:
36:This article
34:
25:
24:
19:
834:. Retrieved
815:
809:
790:
786:
776:
754:(1): 92–96.
751:
747:
741:
713:
709:
668:
664:
661:
657:
653:
649:
645:
641:
637:
633:
629:
625:
621:
617:
613:
609:
605:
604:
600:
596:
592:
588:
584:
580:
576:
572:
568:
564:
560:
556:
552:
551:
543:
539:
535:
528:
524:
520:
513:
509:
505:
504:
499:
495:
489:
485:
481:
475:
471:
467:
462:
458:
454:
451:
450:
444:
440:
436:
432:
425:
418:
411:
404:
397:
390:
388:
385:
377:
373:
366:
362:
356:
352:
346:
342:
333:
329:
324:
316:
312:
305:
301:
289:
285:
278:
271:
267:
261:
251:
241:
234:
225:
219:
215:
209:
205:
202:
197:
193:
186:
182:
175:
171:
167:
163:
161:
141:
129:
125:Golden ratio
121:
112:
108:
88:sorted array
83:
77:
62:
53:
37:
836:January 18,
716:(12): 648.
148:Jack Kiefer
687:References
768:120681132
538:; and if
435:. Assume
158:Algorithm
133:CPU cache
56:July 2013
850:Category
675:See also
644:−
636:−
587:−
575:−
519:, go to
492:−2
478:−1
90:using a
732:7982182
606:Step 4.
553:Step 3.
506:Step 2.
452:Step 1.
403:, ...,
232:, when
115:) (see
42:Please
766:
730:
658:Step 2
601:Step 2
536:Step 4
534:go to
521:Step 3
371:, set
327:. Set
249:, and
82:, the
764:S2CID
728:S2CID
624:) ← (
571:) ← (
527:>
523:; if
512:<
417:<
111:(log
838:2007
652:and
595:and
498:and
439:+1=
266:Set
162:Let
795:doi
756:doi
718:doi
640:, 2
608:If
555:If
508:If
380:− 2
336:− 1
323:to
321:+ 1
277:If
257:= 1
247:= 1
237:≥ 0
119:).
78:In
46:to
852::
789:.
785:.
762:.
752:13
750:.
726:.
712:.
708:.
694:^
632:,
628:+
620:,
616:,
583:,
579:,
567:,
563:,
542:=
484:←
480:,
470:←
466:,
457:←
447:+1
396:,
376:=
369:−2
359:−1
349:−1
332:=
319:−1
308:−1
292:−1
270:=
259:.
239:,
224:+
222:+1
214:=
212:+2
200:.
174:=
840:.
803:.
797::
791:4
770:.
758::
734:.
720::
714:3
669:i
665:i
654:q
650:p
646:p
642:q
638:q
634:p
630:q
626:i
622:q
618:p
614:i
610:p
597:q
593:p
589:q
585:p
581:q
577:q
573:i
569:q
565:p
561:i
557:q
546:i
544:K
540:K
531:i
529:K
525:K
516:i
514:K
510:K
500:q
496:p
490:k
486:F
482:q
476:k
472:F
468:p
463:k
459:F
455:i
445:k
441:F
437:N
433:K
428:N
426:K
422:2
419:K
415:1
412:K
407:N
405:R
400:2
398:R
393:1
391:R
378:k
374:k
367:k
363:F
357:k
353:F
347:k
343:F
334:k
330:k
325:n
317:k
313:F
306:k
302:F
294:.
290:k
286:F
279:k
274:.
272:m
268:k
254:0
252:F
245:1
242:F
235:k
228:k
226:F
220:k
216:F
210:k
206:F
198:n
194:F
189:m
187:F
183:n
178:m
176:F
172:n
168:F
164:k
113:n
109:O
69:)
63:(
58:)
54:(
40:.
20:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.