[Verse 1]
Got a sorted list, a million items long
Need to find one element, can't take too long
Linear search would check them one by one
But binary's the method when you want it done
Start in the middle, that's your first guess
Compare your target, is it more or less
If it's too high, cut the right side out
If it's too low, left side's what it's about
[Chorus]
Cut in half, cut in half, that's the binary way
Log of n, log of n, keeps the time delay
Sorted data, start middle, compare and decide
Eliminate half, then repeat the ride
Cut in half, cut in half, divide and conquer style
O log n complexity makes it all worthwhile
[Verse 2]
Low index zero, high index at end
Middle equals low plus high divided friend
If middle value matches what you seek
Return that index, mission complete unique
But if the target's greater than mid-point
Move low to middle plus one, that's the joint
If target's smaller, high becomes mid minus
Keep the search space tight, that's how we find it
[Chorus]
Cut in half, cut in half, that's the binary way
Log of n, log of n, keeps the time delay
Sorted data, start middle, compare and decide
Eliminate half, then repeat the ride
Cut in half, cut in half, divide and conquer style
O log n complexity makes it all worthwhile
[Bridge]
While low is less than or equal high
Keep searching till you reach the sky
Base case hit when bounds have crossed
Return negative one, element's lost
From million items down to one
In twenty steps your search is done
That's the power of the binary search
Logarithmic time, put efficiency first
[Verse 3]
Recursive version calls itself with bounds
Iterative loops until the answer's found
Both approaches give the same result
Just different styles, neither one's at fault
Remember prerequisite, data must be sorted
Random order makes the algorithm thwarted
Binary search trees extend this concept wide
Self-balancing structures keep efficiency as guide
[Chorus]
Cut in half, cut in half, that's the binary way
Log of n, log of n, keeps the time delay
Sorted data, start middle, compare and decide
Eliminate half, then repeat the ride
Cut in half, cut in half, divide and conquer style
O log n complexity makes it all worthwhile
[Outro]
When you need to find that needle in the stack
Binary search will get you on the right track
Divide the problem, conquer with precision
Logarithmic time, that's the optimal decision