Fibonacci Search is one of those algorithms that feels both clever and refreshing. It takes the popular idea of searching through sorted data and adds a mathematical twist by using the Fibonacci sequence to decide where to check first. If you’ve ever used Binary Search, you already know the general idea of dividing the data and narrowing down your target. Fibonacci Search works in a similar way but uses Fibonacci numbers to split the array into sections. This brings a different kind of balance to the search process and can sometimes make it more efficient on certain kinds of datasets.
with hands-on learning.
get the skills and confidence to land your next move.
What makes Fibonacci Search interesting is how it chooses its mid-point using Fibonacci numbers rather than the usual midpoint formula. Because of this, it reduces the need for direct division operations, which was very helpful in older systems where division was expensive. Even today, it remains a useful teaching algorithm because it helps learners explore searching from a new angle. If you are looking for a clean and instructive algorithm to learn in Swift, Fibonacci Search is a great candidate.
Program 1: Basic Fibonacci Search in Swift
This first program shows the standard version of Fibonacci Search. It uses precomputed Fibonacci numbers to figure out which part of the array to explore.
import Foundation
func fibonacciSearch(_ array: [Int], target: Int) -> Int? {
var fib2 = 0
var fib1 = 1
var fib = fib1 + fib2
while fib < array.count {
fib2 = fib1
fib1 = fib
fib = fib1 + fib2
}
var offset = -1
while fib > 1 {
let i = min(offset + fib2, array.count - 1)
if array[i] < target {
fib = fib1
fib1 = fib2
fib2 = fib - fib1
offset = i
} else if array[i] > target {
fib = fib2
fib1 = fib1 - fib2
fib2 = fib - fib1
} else {
return i
}
}
if fib1 == 1 && offset + 1 < array.count && array[offset + 1] == target {
return offset + 1
}
return nil
}
let data = [3, 8, 12, 19, 25, 31, 42, 56]
if let index = fibonacciSearch(data, target: 25) {
print("Found at index \(index)")
} else {
print("Not found")
}This version is a straightforward implementation of the algorithm. It builds up Fibonacci numbers, then uses them to determine positions inside the array. The offset helps track where the search has already passed, and the algorithm keeps narrowing the range until the target is found. For beginners, this method clearly shows why Fibonacci numbers are useful for splitting the array.
Program 2: Fibonacci Search With a Loop-Based Fibonacci Generator
This second program still performs Fibonacci Search but generates Fibonacci numbers using a looping helper function. This keeps the code organized and easier to understand.
import Foundation
func generateFibonacci(upTo n: Int) -> (Int, Int, Int) {
var f2 = 0
var f1 = 1
var f = f1 + f2
while f < n {
f2 = f1
f1 = f
f = f1 + f2
}
return (f, f1, f2)
}
func fibonacciSearchLoop(_ array: [Int], target: Int) -> Int? {
let (fib, fib1Start, fib2Start) = generateFibonacci(upTo: array.count)
var fibM = fib
var fib1 = fib1Start
var fib2 = fib2Start
var offset = -1
while fibM > 1 {
let i = min(offset + fib2, array.count - 1)
if array[i] < target {
fibM = fib1
fib1 = fib2
fib2 = fibM - fib1
offset = i
} else if array[i] > target {
fibM = fib2
fib1 = fib1 - fib2
fib2 = fibM - fib1
} else {
return i
}
}
if fib1 == 1 && offset + 1 < array.count && array[offset + 1] == target {
return offset + 1
}
return nil
}
let numbers = [4, 7, 9, 15, 22, 38, 49]
if let index = fibonacciSearchLoop(numbers, target: 22) {
print("Found at index \(index)")
} else {
print("Not found")
}By breaking out the Fibonacci generation into its own helper function, this program feels more readable. It also helps beginners focus on understanding how the main search loop functions without being distracted by Fibonacci number generation logic.
Program 3: Fibonacci Search with Recursion for Generating Fibonacci Numbers
This version uses recursion to generate Fibonacci numbers before beginning the search. It does not use recursion for the search, only for building the Fibonacci sequence.
import Foundation
func fibRecursive(_ n: Int) -> Int {
if n <= 1 {
return n
}
return fibRecursive(n - 1) + fibRecursive(n - 2)
}
func largestFibLessThan(_ n: Int) -> (Int, Int, Int) {
var k = 0
while fibRecursive(k) < n {
k += 1
}
return (fibRecursive(k), fibRecursive(k - 1), fibRecursive(k - 2))
}
func fibonacciSearchRecursiveFib(_ array: [Int], target: Int) -> Int? {
let (fib, fib1Start, fib2Start) = largestFibLessThan(array.count)
var fibM = fib
var fib1 = fib1Start
var fib2 = fib2Start
var offset = -1
while fibM > 1 {
let i = min(offset + fib2, array.count - 1)
if array[i] < target {
fibM = fib1
fib1 = fib2
fib2 = fibM - fib1
offset = i
} else if array[i] > target {
fibM = fib2
fib1 = fib1 - fib2
fib2 = fibM - fib1
} else {
return i
}
}
if fib1 == 1 && offset + 1 < array.count && array[offset + 1] == target {
return offset + 1
}
return nil
}
let values = [5, 10, 18, 27, 36, 45, 60]
if let index = fibonacciSearchRecursiveFib(values, target: 36) {
print("Found at index \(index)")
} else {
print("Not found")
}This approach gives learners a chance to see recursion in a supporting role. The search itself stays iterative, but the Fibonacci numbers come from a recursive function. This helps beginners see how recursion can be used safely without making the main algorithm complicated.
Program 4: Step-By-Step Tracing Version
This version prints every important step, giving beginners a clear window into how the algorithm narrows down the search area.
import Foundation
func fibonacciSearchTrace(_ array: [Int], target: Int) -> Int? {
var f2 = 0
var f1 = 1
var f = f1 + f2
while f < array.count {
f2 = f1
f1 = f
f = f1 + f2
}
var offset = -1
while f > 1 {
let i = min(offset + f2, array.count - 1)
print("Checking index \(i), value \(array[i])")
if array[i] < target {
print("Going right")
f = f1
f1 = f2
f2 = f - f1
offset = i
} else if array[i] > target {
print("Going left")
f = f2
f1 = f1 - f2
f2 = f - f1
} else {
print("Found target")
return i
}
}
if f1 == 1 && offset + 1 < array.count && array[offset + 1] == target {
print("Found at last check")
return offset + 1
}
return nil
}
let items = [1, 4, 9, 13, 21, 34, 55]
if let index = fibonacciSearchTrace(items, target: 34) {
print("Found at index \(index)")
} else {
print("Not found")
}This tracing version is perfect for beginners who want to see exactly how the algorithm jumps between Fibonacci partitions. Watching each step helps gain confidence and understanding.
Program 5: Fibonacci Search as a Swift Extension
The final version adds Fibonacci Search to the Array type. This makes the algorithm feel like a natural part of the language, because you can call it directly on any sorted list just like any other built-in method. It keeps the code clean, reduces repetition, and gives beginners a simple way to reuse the search logic across different programs.
import Foundation
extension Array where Element: Comparable {
func fibonacciSearch(target: Element) -> Int? {
var fib2 = 0
var fib1 = 1
var fib = fib1 + fib2
while fib < self.count {
fib2 = fib1
fib1 = fib
fib = fib1 + fib2
}
var offset = -1
while fib > 1 {
let index = Swift.min(offset + fib2, self.count - 1)
if self[index] < target {
fib = fib1
fib1 = fib2
fib2 = fib - fib1
offset = index
} else if self[index] > target {
fib = fib2
fib1 = fib1 - fib2
fib2 = fib - fib1
} else {
return index
}
}
if fib1 == 1 && offset + 1 < self.count && self[offset + 1] == target {
return offset + 1
}
return nil
}
}
let items = [3, 6, 11, 19, 24, 32, 45]
if let index = items.fibonacciSearch(target: 32) {
print("Found at index \(index)")
} else {
print("Not found")
}This approach is very enjoyable for many Swift learners because it turns Fibonacci Search into a friendly and reusable tool. Once added as an extension, the algorithm becomes easy to call and does not require rewriting the search logic each time. It is a great example of how Swift’s extension features can make algorithms feel neat and modular while keeping the main code simple.
Frequently Asked Questions (FAQ)
This section answers a few common questions that often come up while learning Fibonacci Search and practicing the Swift examples.
Q1. Why does Fibonacci Search require a sorted array?
It moves by comparing values at calculated positions. Without sorted data, those comparisons would not tell the algorithm whether to move left or right.
Q2. Is Fibonacci Search better than Binary Search?
They are very close in speed, but Fibonacci Search avoids division, which can be useful in systems where only simple arithmetic is cheap and fast.
Q3. Why do Fibonacci numbers matter in this algorithm?
They create a smooth pattern of checking positions that grows in a natural way. This reduces overhead and keeps the algorithm lightweight.
Q4. Can I use Fibonacci Search on strings or other types?
Yes, as long as the data is sorted and can be compared, the algorithm works fine.
Q5. Do modern programs still use Fibonacci Search?
It appears mostly in special-purpose systems, but it is still taught because it shows how mathematical ideas can shape an efficient search method.
Conclusion
Fibonacci Search is a clever and elegant searching technique that uses the beauty of Fibonacci numbers to explore data in a structured way. While it may not be as common as Binary Search today, learning it gives beginners a deeper understanding of how different algorithms think and move. Swift makes the implementation smooth, and exploring different versions—from simple loops to recursion and extensions—helps build stronger problem-solving skills. As you practice, you will notice how each program version reveals a new angle of the algorithm. Keep experimenting, and soon searching through sorted data in Swift will feel natural and rewarding.
