Dark Mode

2,946 views

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

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

0

edited
Jun 20, 2021
by ASNR1010

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

0

28 votes

Best answer

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

4

edited
Oct 4, 2019
by Nirmal Gaur

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

3

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

0

1

–1 vote

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.

0