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

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

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

19 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.**

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 ?

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[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) **

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.

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.