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!