[Verse 1]
Started with a sorted array, million elements deep
Binary search is solid but we need that extra leap
When the target's way out there, beyond our current range
Exponential stepping up, time to make a change
Start at index one, then double up the bound
Two, four, eight, sixteen, watch those numbers pound
Keep on doubling till we overshoot our mark
Found our range window, now we're cooking in the dark
[Chorus]
Double up, double up, find that upper bound
Binary finish when the range is found
Exponential search, O log n time
Skip the middle, jump ahead, algorithm so prime
Double up, double up, then divide and seek
Best of both worlds when your target's unique
[Verse 2]
Unbounded arrays calling, infinite they seem
Don't know the size limit, living in a dream
Regular binary can't handle unknown space
Exponential preprocessing sets the perfect pace
Growth is geometric, powers of two we ride
Till we hit the ceiling or step outside
Then we narrow down with binary precision
Smart preprocessing leads to quick decision
[Chorus]
Double up, double up, find that upper bound
Binary finish when the range is found
Exponential search, O log n time
Skip the middle, jump ahead, algorithm so prime
Double up, double up, then divide and seek
Best of both worlds when your target's unique
[Bridge]
When your data's sparse and targets far away
Exponential cuts through like a razor blade
Two phase approach, expand then contract
Mathematical beauty, that's a proven fact
Linear search too slow, binary needs bounds
Exponential bridges gaps with leaping sounds
[Verse 3]
Implementation clean, two functions in the mix
First one finds the range, second one gets the fix
While the bound's less than our target value here
Double up the bound, make that range more clear
Once we overshoot, we know we're in the zone
Binary takes over, brings our target home
Best case logarithmic, worst case still the same
Exponential search earned its place in the game
[Outro]
Double to find, binary to seek
Exponential power for the targets that you need
From one to infinity, we'll track them down
Algorithm mastery, wear that coding crown