TIFR CSE 2012 | Part B | Question: 11

Question

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?

• A. Only Program $1$ is correct
• B. Only Program $2$ is correct
• C. Only Program $1$ and $2$ are correct.
• D. Both Program $2$ and $3$ are correct
• E. All the three programs are wrong

Comments

Similar question

https://gateoverflow.in/394/gate2008-84

https://gateoverflow.in/43508/gate2008-85

---

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

---

@JashanArora I think you need to swap the conditions.

Answer 1

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.

Comments

@MRINMOY_HALDER

in which line?

---

last line of program 2 & 3

---

Program 1 fails even when you are finding the last element of the array.

Answer 2

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.

Answer 3

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

Comments

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