2,946 views

The first $n$ cells of an array $L$ contain positive integers sorted in decreasing order, and the remaining $m - n$ cells all contain 0. Then, given an integer $x$, in how many comparisons can one find the position of $x$ in $L$?

1. At least $n$ comparisons are necessary in the worst case.
2. At least $\log m$ comparisons are necessary in the worst case.
3. $O (\log (m - n))$ comparisons suffice.
4. $O (\log n)$ comparisons suffice.
5. $O (\log (m / n))$ comparisons suffice.

This was easiest question of all.
as we know there are first n elements and remaining all are zero so  we dont need to apply binary search for remaining elements we can simply apply on the first n elements that will take  O(logn)  as the later half is already zero
edited by

why everybody is finding the position of n. Isn’t this is given in question first n. so, we just need to apply binarySearch(a,1,n) and that’s it. It gives the answer.

If he literally wants to find us then he can say something like this,

their is an array which contains some elements in decreasing order from beginning and rest elements are zero.

then in this we have to find value of n as we don’t know and question doesn’t told explicitly n or something.

anyone give suggestion and correct me if I’m thinking wrong...

(d) $\mathbf{O(\log n)}$ comparisons suffice.

Since it is possible that $m \ggg n$, we need to restrict ourselves to the first $O(n)$ elements to perform the binary search.

We start with the first element (index $i=1$), and check if it is equal to $0$. If not, we double the value of $i$, and check again. We repeat this process until we hit a $0$.

i = 1;
while(arr[i] != 0)
i *= 2;  

Once we hit a $0$, the largest possible value (worst case) of $i$ can be $2n-2$. This will happen if $n = 2^k+1$ for some $k$. Then, our 2nd last value of $i$ will be $2^k$, and then we get $2^{k+1}$, which is equal to $2n-2$.

Now that we've hit a $0$, and the array contains positive numbers in decreasing order, if $x$ is present in $L$, it must be in the first $i$ elements.

We can binary search the first $i$ elements in $O(\log i)$ comparisons.

Since the largest possible value of $i = 2n-2$, our algorithm takes $O \Bigl (\log (2n-2) \Bigr ) = O(\log n)$ comparisons.

edited

Actually, this will be much faster in practice. Still $O(\log n)$ though.

if x<0: return
i = 1
while arr[i] > x:
i *= 2
binary_search(arr, bottom = i/2, top = i)

Questions says

The first n cells of an array L contain positive integers sorted in decreasing order

We could apply binary search on $L[1\dots n]$ and thus $O(logn)$ comparisons would suffice.

What is the reason for assuming that $n$ (or for that matter $m$) is not known?

How the largest worst case value of i is 2n-2.
edited

In the best case, i would be a closest possible index to n, meaning n is in powers of 2, that is, $n = 2^{k}$.

In the worst case, i would be fartest to n, this will happen when $n = 2^{k}+1$ (think!), we would be at $i=$$2^{k}$ but we still do not hit the 0, so we take $i=2^{k+1}$ $=2.2^{k}$ $=$ $2(n-1) = 2n-2$.

Option D should be the correct answer.

ASSUMPTION: $0$ indexing of array $L$.

Pseudo code for finding the correct position of $x$ in array $L$ will be as follows:

if (x <= 0)
return (m + 1);
else
return MODIFIED_BIN_SEARCH(0, n - 1, x);

Code for Modified Binary Search:

MODIFIED_BIN_SEARCH (low, high, x){
if (low > high)
return mid; //Exit point for unsuccessful searches.
mid = ( low + high )/2;
if ( x == a[mid])
return mid; //Exit point for successful searches.
else if (x > a [mid])
return MODIFIED_BIN_SEARCH (low, mid - 1, x);
else
return MODIFIED_BIN_SEARCH (mid + 1, high, x);
}

In the above pseudo code for finding correct position of $x$ in array $L$

If $x <= 0$, only one comparison will be required,

If $x > 0$,

$1$ comparison for checking $x > 0$ and,

$O(\log n)$ comparisons in MODIFIED_BIN_SEARCH(1, n, x) will be required irrespective of whether the search is successful or unsuccessful.

Worst Case : $x > 0$ & search for $x$ in array $L$ is unsuccessful.

Clearly worst cases will require $1 + O(\log n)$ which in turn, is same as $O(\log n)$ comparisons.

Hence option D should be correct.

Example of Unsuccessful Search:

Let $n = 5$,

First $n$ elements of $L$ be: $8, 6, 5, 3, 1$, and

$x = 2$.

Then clearly $x > 0$,

also MODIFIED_BIN_SEARCH(0, 4, 2) will return $4$,

so pseudo code for finding correct position of $x$ in array $L$ will return $4$, which is correct.

Array $L$ after inserting $2$ will be: $8, 6, 5, 3, 2, 1$.

Example of Successful Search :

Here we are inserting an element that is already present in $L$,

Let $n = 5$,

First $n$ elements of $L$ be: $8, 6, 5, 3, 1$, and

$x = 6$.

Here also clearly $x > 0$,

MODIFIED_BIN_SEARCH(0, 4, 2) will return position of $6$ in $L$ that is $1$,

so pseudo code for finding correct position of $x$ in array $L$ will return $1$, which is correct.

Array $L$ after inserting $x$ will be: $8, 6, 6, 5, 3, 1$.

Okay, no harm in assuming $n$ is not given.

But if $m$ is also not given then the worst case will be when $x$ is a - ve integer.

Then we have to find $m$ first,

and based on your answer to this question this should require $O(\log m)$ comparisons, and option B should be the correct answer right?

You're not given the value of $n$, and possibly not even the value of $m$. You only have the array.

So, you can't do this:

MODIFIED_BIN_SEARCH(0, n - 1, x);
Thanks for edit.

Yes you are right, in case $n$ is not given we first have to find $n$ to perform efficient binary search.

I could have misinterpreted the question.

But how did you inferred that $n$ is not given, I missed that part?

Here till 'n' we have number in decreasing order if we consider all are distinct then it will take O(logn) time to find the position of a number
but if the number are repeated then we can't apply the binary search linear search will be applicable O(n).

so we can say  A) At least n comparisons are necessary in the worst case.

@Umang: ohkk. But you can also find the occurrence of $a[i]=i$ in $O(\log n)$ time :P
i am saying we have to find any element a[i] such that a[i]==i if elements are repeated not distinct.
In this case we dont know which side to go?

No, we do know which side to go in binary search. Because in that case, our binary search condition won't be $arr[i]>x$ or $arr[i]<x$

//note: array is descending, while the indices are ascending.
if(arr[mid] > mid)
low = mid;
else if(arr[mid] < mid)
high = mid;