hereiam

A binary search realisation about the 1972 Stealer's Wheel song "Stuck in the Middle With You" that went too far...

Quality Status: Gold Master

Functionality Status: Complete

License: BSD 3-Clause

The lyrics to the song "Stuck in the Middle With You" by Stealer's Wheel famously go: "Clowns to the left of me, jokers to the right here I am stuck in the middle with you". This came on the radio as I was driving one day, and coincidentally I had been practising DSA for interviews around this time. There we have the dumbest realisation ever: that lyric forms a monotonic condition that is ideal for performing binary search.

We can form the following LeetCode-esque problem statement:

• Given a fixed-length array of people (represented by integers) where the condition holds that there is a person stuck in the middle somewhere, with only "clowns" to the left of him, and only "jokers" to the right of him, write an algorithm that returns the exact index where he is stuck.

The steps that the binary search algorithm takes to find his position are very simple:

1. Initialise a pointer at the start of the array and the end of the array forming upper and lower bounds,
2. Calculate the midpoint of the upper and lower bounds, then check the value of that position,
3. If it is a clown, the person must be stuck to the right of them, since only clowns are to his left. Adjust the lower bound to equal the midpoint + 1, or:
4. If it is a joker, the person must be stuck to the left of them, since only jokers are to his right. Adjust the upper bound to equal the midpoint - 1,
5. Repeat steps 2-4 until the person is found.

I have written a very short (< 200 LOC) program to demonstrate this. It will generate an array with a random number of clowns and jokers, and place the guy in the middle then solve it using binary search. The user can specify how many people there are in total and it prints out its steps using emojis (cringe, I know - make sure your terminal supports unicode). For lyrical accuracy it includes his girlfriend in the array as well - stuck in the middle with you.

• hereiam-master-bb2e934.tar.gz

Video Feature - You can Binary Search SONG LYRICS???