# TIFR2012-B-11

882 views

Consider the following three version of the binary search program. Assume that the elements of type $T$ can be compared with each other; also assume that the array is sorted.

i, j, k : integer;
a : array [1....N] of T;
x : T;

Program 1 :   i := 1; j := N;
repeat
k := (i + j) div 2;
if a[k] < x then i := k else j := k
until (a[k] = x) or (i > j)
Program 2 :   i := 1; j := N;
repeat
k := (i + j) div 2;
if x < a[k] then j := k - 1;
if a[k] < x then i := k + 1;
until i > j
Program 3 :=  i := 1; j := N
repeat
k := (i + j) div 2;
if x < a[k] then j := k else i := k + 1
until i > j

A binary search program is called correct provided it terminates with $a[k] = x$ whenever such an element exists, or it terminates with $a\left [ k \right ]\neq x$ if there exists no array element with value $x$. Which of the following statements is correct?

1. Only Program $1$ is correct
2. Only Program $2$ is correct
3. Only Program $1$ and $2$ are correct.
4. Both Program $2$ and $3$ are correct
5. All the three programs are wrong

edited
0
related to gate 2008 quetion.
6
1

This kind of question is basically testing knowledge of progress, loop invariant and loop termination condition.

But in worst case many cases(on small array) could be formed to get an idea, where a given program may fail.

Case 1.1 (Array is of even length and element do not lie in the array)

Case 1.2 (Array is of even length and element lie in the array)

Case 2.1 (Array is of odd length and element do not lie in the array)

Case 2.12(Array is of odd length and element lie in the array)

Case 3 Array is empty.

For above mentioned cases also consider scenario if element are distinct or all are same.

0
Option B is correct. We needn't worry about the equality condition.
0 For iterative version of binary search...

$k = (i+j)/2$

If the array element $< x$

$j = k-1$

If the array element $> x$

$i=k+1$

If array element $= x$

return $k$

The given programs have one or the other thing wrong. Option E

0
@JashanArora I think you need to swap the conditions.

First program wont work if array has elements same..it may go into infinite loop .To make it work it properly we have to do following changes $j=k-1$  and $i=k+1$

For second program $a[k]==x$ condition is missing so it is wrong

Third program is also wrong as $j!=k-1$ and condition $a[k]==x$ is missing

edited
4

@Pooja Palod ji,

I think 3rd program is wrong only because a[k]==x is missing. Even if condition j!=k-1 is not  there it will work. am i correct ?

7

9

In third program even if we ignore a[k]==x condition, it's still incorrect.
array is of size 5, each cell contains 2 and we are looking for 1,
k = (5+1)/2 = 3, 1< A hence j=3
k = (1+3)/2 = 2, 1<A, hence j=2
k = (1+2)/2 = 1, 1<A, hence j=1
K = (1+1)/2 = 1, 1<A, hence j=1 (infinite loop)

2
YES THIRD PRORAM FAILS WHEN ALL ELEMENTS ARE SAME SAY(2,2,2,2,...2)AND WE ARE SEARCHING FOR SAY 1 EVEN IF A[K]==X CONDITION IS PRESENT...
0

@sushmita

also in 3rd program missing j=k-1

because j=k may satisfy infinite loop

right?

1

yes @srestha it will fall under infinite loop

0
srestha

what is the meaning of untill (i > j) ???

program will run upto (i <= j) ?
0

@MRINMOY_HALDER

in which line?

0
last line of program 2 & 3
Program 1 & 3 are errorneous Cz they have improper index (i,j)updation .

It will go into infinite loop when we r searching for an element and that is not present in the array.

It should be i=k+1 ; j= k-1;

Program 2 is incorrect cz a[k]=x condition is not there.

So option e. All options are wrong.
Small Doubt

Program 2 and Program 3 says
Loop Says That
Repeat until i > j

i=1 and j =N
i is never greater than j so Will the loop Even Execute after one time ???
1

Until is exactly opposite of while loop. Thus, it repeats the code inside its body till its condition is false.

## Related questions

1
332 views
This question concerns the classes $P$ and $NP.$ If you are familiar with them, you may skip the definitions and go directly to the question. Let $L$ be a set. We say that $L$ is in $P$ if there is some algorithm which given input $x$ decides if $x$ is in $L$ or not ... $\text{MATCH} \notin P\text{ and } \overline{\text{MATCH}} \notin P$ none of the above
Consider the quick sort algorithm on a set of $n$ numbers, where in every recursive subroutine of the algorithm, the algorithm chooses the median of that set as the pivot. Then which of the following statements is TRUE? The running time of the algorithm is $\Theta (n).$ The running time ... algorithm is $\Theta (n^{1.5})$. The running time of the algorithm is $\Theta (n^{2})$. None of the above.
An array $A$ contains $n$ integers. We wish to sort $A$ in ascending order. We are told that initially no element of $A$ is more than a distance $k$ away from its final position in the sorted list. Assume that $n$ and $k$ are large and $k$ is much smaller ... with constant $.n \log k$ comparisons but not with fewer comparisons. $A$ can be sorted with constant $.k^{2}n$ comparisons but not fewer.
Let $n$ be a large integer. Which of the following statements is TRUE? $2^{\sqrt{2\log n}}< \frac{n}{\log n}< n^{1/3}$ $\frac{n}{\log n}< n^{1/3}< 2^{\sqrt{2\log n}}$ $2\sqrt{^{2\log n}}< n^{1/3}< \frac{n}{\log n}$ $n^{1/3}< 2\sqrt{^{2\log n}}<\frac{n}{\log n}$ $\frac{n}{\log n}< 2\sqrt{^{2\log n}}<n^{1/3}$