[Verse 1]
Start with one then double the bound
When your target ain't easily found
Linear search is way too slow
Exponential's the way to go
Jump by powers of two each time
Until you pass your target line
One two four eight sixteen rise
Growing bounds before your eyes
[Chorus]
Double jump until you overshoot
Then binary search to find the root
Exponential then divide and conquer
Time complexity makes you stronger
Oh en log en that's the key
Unbounded arrays set you free
Double jump until you overshoot
Then binary search to find the root
[Verse 2]
When the size is undefined
And the data's not confined
Start at index number one
Keep on doubling til you're done
Found a value that's too high
Now you know your upper sky
Lower bound is half of that
Binary search where it's at
[Chorus]
Double jump until you overshoot
Then binary search to find the root
Exponential then divide and conquer
Time complexity makes you stronger
Oh en log en that's the key
Unbounded arrays set you free
Double jump until you overshoot
Then binary search to find the root
[Bridge]
Two phases make it work so clean
First phase finds the range between
Second phase cuts down the space
Binary search picks up the pace
Sorted data is required
Infinite streams get you fired
Up to search beyond the known
Exponential claims the throne
[Verse 3]
Implementation's crystal clear
Set your low and high frontier
While the high index is less
Than your target under test
Double high and set low too
Previous high's the clue for you
When you overshoot the mark
Binary lights up the dark
[Chorus]
Double jump until you overshoot
Then binary search to find the root
Exponential then divide and conquer
Time complexity makes you stronger
Oh en log en that's the key
Unbounded arrays set you free
Double jump until you overshoot
Then binary search to find the root
[Outro]
From the known into unknown
Exponential search has grown
Doubling bounds then cut in half
Efficient search is quite a craft