the sorted Array and the scanner problem continued…

Wherein the previous post gave the efficient step size for this problem, but there is still a scope of improvement.  Suppose the array size is 100, with our approach the maximum number of comparisons required would be 10+9 = 19. Could we beat this? Yes, I suppose. What if rather than having a fixed step size of sqrt(n) throughout the algorithm, we opt for dynamic step size. Let’s start with step size 18 and see if we could beat our previous answer of 19. The first comparison will happen at 18^th element and if the search element lies in this group then we need another 17 linear comparisons in worst case to find the element in that group making a total of 18 comparisons. Now if the search element is greater than 18^th element then we have to consider the next group. And here lies the secret.  We decide to shrink the next group size by 1, so that this group has 17 elements rather than 18. The reason for this is, we want the total comparisons to be strictly 18 in worst case and since we have already used up one comparison at 18^th element, we have only 17 remaining. Thus to search the element in the second group we need 16 more comparisons and hence making the total comparisons equal to 16+1+1=18 in worst case. Now what we really have to do is to continue this idea until all 100 elements are exhausted. So the group size continues to reduce by 1 at each stage. Hence the third group would have 16, fourth would have 15, fifth would have 14 and so on and so forth.

This algorithm makes sure that we won’t cross the count of 18 comparisons at any cost. But why is it only the number 18? Why not 17? Yes 17 would just do fine. Even the number 16 does remarkably well. But again, as with the previous post what’s the ideal value to start with, since we cannot go forever reducing the number. The only cue we have at this point is whatever count we start with, it should assure us that it covers all the 100 elements. Suppose we start with step size equal to 10 and at each successive group we reduce the group size by 1 to maintain the count. But all the groups so formed doesn’t cover all the 100 elements since the total elements covered in all groups is

10 + 9 + 8 + . . . . . . + 3 + 2  + 1 = (10*11)/2 = 55

So step size 10 covers only 55 elements. Though it failed to be an ideal answer it did give us an insight to find the one. If we start with step size equal to x then the total number of elements covered by the groups formed by x is

x + (x-1) + (x-2) + . . . . . . + 3 + 2 + 1

=∑ x 

Thus the only condition that makes x the ideal choice is that the above summation should cover all the n elements in the array. Hence we have a new equation –

∑ x ≥ n

(x*(x+1))/2 ≥ n

=>  x² + x ≥ 2n

i.e.  x² + x  - 2n ≥ 0

Since we are looking for least value of x,

x² + x  - 2n = 0

And the solution for this is

x = (-1 ± √ (–1 – 8n))/2

For integer value,

x = ceil ((√ (8n + 1) -1)/2)

Thus for n = 100, x comes to be 14 and I bet you can’t beat this!

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...