the sorted Array and the scanner problem

I came across this puzzle during my Msc(Engg) interview in IISc Bangalore. The puzzle was simple and stated as -

"You are given a sorted array of length n and a pointer that points to the first element in the array. This is a special pointer that can be reversed in direction only once. That means if it was moving to right and then it decides to move towards left then it keeps on moving to left. It cannot change its direction again."

The problem is to come up with an efficient algorithm to search a number in the array.

While it took me fews seconds to put all the conditions and situations together, my first response was to do a linear search. And that was accepted quite generously. Of course, the next question as anticipated was "Can you do better?"

This algorithm had a running time of n. So I decided to divide the array into two parts. I suggested directly compare the middle element with the search element and depending upon the outcome, we move into either of the half. This reduced the running time to n/2. That too was accepted cordially and followed by the same question!

Instead of targeting the middle element, we could target, say n/3^th element. So running time is down to n/3 from my first response of n. Next question was a bouncer.

"So what's the appropriate step size that gives the best efficiency?"

He meant, we could go endlessly by choosing n/5 ^th, n/10 ^th, n/20 ^th and so on. Which one of them would be the best?

Suddenly I recalled a similar problem that I had read long back on 20bits.com, which tries to find similar solution. But I couldn’t recollect the way he had solved, probably because four IIsc professors were continuously gazing me. I tried recollecting and gave up. But I gave them a brief idea how could we find the solution. They looked satisfied with my broken answer and asked me to ponder upon it after the interview.

Soon, I was heading back home in a BMTC bus. My mind was completely occupied with calculations and trying to find the solution for that problem. But I did it! I found it in BMTC!!

It was not that difficult as it sounded in the interview room. We wanted to find the step size that would lead best efficiency. So If I choose n/3 step size, then once finding the appropriate partition I had to do a linear search for remaining 2 elements in the partition. The explanation being, since each partition had 3 elements and one of them gets compared at each step size, I had to check the remaining 2 using linear search. What if I take step size n/10? I needed to check another 9 elements using linear search in the partition.

So, mathematically put, the total number of comparisons required –

n/s + (s-1)

where

n -> array length and s -> step size.

This equation preciously defines the number of comparisons required for a generic step size s. The first part of the equation: n/s, indicates the number of partitions that are formed due to step size s and these were the number of comparisons required on the step size in worst case, as the search element could be in the last partition. The other part: (s-1), indicates the number of linear comparisons required once we found our partition. Since each partition had s elements and one of them was already compared during partition searching, we required only s-1 more comparisons.

Now we have a mathematical representation of the problem we are dealing with and we just needed to find the step size that resulted into minimum comparisons. Hence we simply needed to find the value of s where the above equation had a minima. And that’s typical differentiation stuff. We differentiate the above equation wrt s and equate it to zero to get the required value of s.

Thus on differentiating and equating the above equation to zero,

-n/s² +1 =0

=> n = s²

Or s = √n

 i.e. s = sqrt(n)

And that’s it!

continued...