621 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 | 621 views
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

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

by Boss (31.4k points)
edited
+3

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

+6

+7

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)

+1
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.
by Boss (23.9k points)
–1 vote
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 ???
by Active (4.5k points)
0

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