TIFR CSE 2011 | Part B | Question: 39

Question

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

• A. At least $n$ comparisons are necessary in the worst case.
• B. At least $\log m$ comparisons are necessary in the worst case.
• C. $O (\log (m - n))$ comparisons suffice.
• D. $O (\log n)$ comparisons suffice.
• E. $O (\log (m / n))$ comparisons suffice.

Comments

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

---

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

Answer 1

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

Comments

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.

---

@sutanay3

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

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

Comments

It means that "On unsuccessful searches we are not concerned about finding the correct position for $x$ at which it should be be inserted." ??

---

Which question are you even reading? This question says nothing about inserting elements. It just asks for the worst case comparisons of search for a given element $x$.

---

Alright, we just have to perform look ups on L for x.

so no need to worry about -ve values of x.

Thank you.

Answer 3

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.

Comments

@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;