The Gateway to Computer Science Excellence
+16 votes
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
in Algorithms by Boss (30.7k points)
edited by | 621 views
0
related to gate 2008 quetion.
+6
I found the same qsn frequently asked. Asked Indirectly.
+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

3 Answers

+16 votes
Best answer

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

So, answer is E.

by Boss (31.4k points)
edited by
+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

Chhotu 

yes, your observation is correct..

+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[3] hence j=3
k = (1+3)/2 = 2, 1<A[2], hence j=2
k = (1+2)/2 = 1, 1<A[1], hence j=1
K = (1+1)/2 = 1, 1<A[1], 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
+5 votes
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.

Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,741 questions
57,251 answers
198,059 comments
104,692 users