retagged by
2,494 views
22 votes
22 votes

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
retagged by

3 Answers

Best answer
21 votes
21 votes

The first program wont work if array has all elements the same in which case it goes into infinite loop. To make it work properly we have to do the following changes $j=k-1$  and $i=k+1$

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

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

So, answer is E.

edited by
6 votes
6 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.
0 votes
0 votes
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 ???
Answer:

Related questions

18 votes
18 votes
3 answers
1
makhdoom ghaya asked Nov 2, 2015
3,626 views
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...