Last Sunday when I was sipping my evening tea, my daughter came to me and said with annoyance, “Papa, I did not pluck the flowers and no one is believing me. How can I prove it?”.
The lockdown is still effect in many parts of the country and I am allowed to work from home. As the lockdown prolonged, so the WFH facility, the home in the city of office eventually changes to home in native town. So we moved from Hyderabad to Angul, a town in Odisha.
Unlike Hyderabad, where we are staying in an enclosed 4 walls of 2 bed room flat, in Angul we have our own porch, backward and a garden. I was sitting under the porch looking towards the garden when my daughter complained.
My daughter studies in class 3 and plays with her cousin sister most of the time after her short online classes. Sometimes I suspects while playing with their imaginary friend Pinkie Pie, they forget the real world. But I listened to her complain and asked her to tell me the whole story.
She directed me to a flower plant and continued. There was a flower in it and now it is not, and everyone is blaming me that I have plucked it. How can I prove that I have not done this. I thought for a moment and said, “why can’t you replay the videos of security camera and check?” I knew it was not easy to review the fast forward videos manually and not sure how many of the previous days videos have to be reviewed. However I said that on the instinct of fast thinking process.
It will take a lot of time. She protested. I agreed and started thinking slow. After a while my eye lit up for the solution and for a possibility of an opportunity.
The videos of the security camera can be seen from the last Sunday, when everyone was admiring it.
The time between the Sundays is 7 days x 24 hours = 168 hours.
So, if we want to see the entire videos of 7 days, that would take 168 hours and loads of patience.
Let’s say, we fast forward the videos with 4x, we have to spend 48 hours to identify the culprit.
If we see the current videos, the flower will definitely not be present. That means, if we fast rewind the videos, we will find a video frame where the flower would not be present. However that would also take the same 168 hours, if the flower is plucked immediate after its admiration session.
We have a better idea, we can divide the 7 days into two equal parts — SUN, MON, TUE, WED and THU, FRI, SAT, SUN. Now, let’s check the video frame of mid night between WED and THU. If we found the flower, then we will review the videos from the second group, starting from 12AM of THU, otherwise the review will be done from first group, starting from SUN.
However we have the liberty of dividing either of the groups and its relevant subgroup again and again. In this way we will find a day for which the flower would not be present for its next day.
Afterwards, we can divide the day again into 2 parts of 12 hours each and repeat the earlier steps again to find a single frame where the flower being plucked to see the culprit with action.
Binary search algorithm
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search…