edited by
3,959 views
17 votes
17 votes

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

3 Answers

Best answer
28 votes
28 votes

(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 by
2 votes
2 votes

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

–1 votes
–1 votes

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.

Answer:

Related questions

39 votes
39 votes
4 answers
1
17 votes
17 votes
2 answers
2