GATE CSE 2008 | Question: 84

Question

Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. 

 f (int Y[10] , int x) {
    int i, j, k;
    i= 0; j = 9;
    do {
        k = (i+ j) / 2;
        if( Y[k] < x) i = k;else j = k;
        } while (Y[k] != x) && (i < j)) ;
    if(Y[k] == x) printf(" x is in the array ") ;
    else printf(" x is not in the array ") ;
 }

On which of the following contents of $Y$ and $x$ does the program fail? 

• A. $Y$ is $[1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8 \ 9 \ 10]$ and $x < 10 $  
• B. $Y$ is $[1 \ 3 \ 5 \ 7 \ 9 \ 11   \ 13 \ 15 \ 17 \ 19]$ and $x < 1 $ 
• C. $Y$ is $[2 \  2 \ 2 \ 2 \  2 \  2 \  2 \ 2 \ 2 \ 2]$ and $x > 2$ 
• D. $Y$ is $[2 \ 4 \ 6 \ 8 \ 10 \ 12 \ 14 \ 16 \ 18 \ 20]$ and $ 2 < x < 20$ and $x$ is even

Comments

this question  Code will give Problem when we will try to access rightmost element or greater than that So except $C$ in each option we are excluding the right most element that's why this implementation is not any problem for these options .

---

Option C

Y=[2,2,2,2,2,2,2,2,2,2]

and

x>2

Take: x=3

When i=8 , j=9
k=8

then i = k = 8

Nothing changes!

State remains forever: i=8 j=9 k=8

Infinite loop ❌ 

so it will go into infinite loop and after some time program STOP ! 

Answer C

---

Option C

Y=[2,2,2,2,2,2,2,2,2,2] ;

and

x>2

Take: x=3

When i=8 , j=9
k=8

then i = k = 8

Nothing changes!

State remains forever: i=8 j=9 k=8

Infinite loop ❌ 

so it will go into infinite loop and after some time program STOP ! 

Answer C  : Y is [2,2,2,2,2,2,2,2,2,2]  and x > 2

Answer 1

when it is option C the control will continue to iterate as $i=8$ and $j=9$;
again and again $i$ will be assigned $k$ which itself equals $8$ as $\frac{8+9}{2}$ being stored in an integer type variable, will evaluate to $8$.

---

For option A, with $x=9, k$ will take the following values:

• $4$
• $6$
• $7$
• $8 - y[8] = 9, x$ found

For option D, with $x=10, k$ will take the following values:

• $4, y[4] = 10, x$ found

Comments

the loop condition: while (Y[k] != x && (i < j))
is meant to stop when found or when i >= j.

0 = 0 hence stop and no infinite loop here

---

why loop is not terminatinng in C case i mean j = n-1 given right so at last element i = j so loop should terminate by same logic given by people above that in case if element lower than first element than i = j

---

It'll not become i=j
There will be final case where i=8 and j=9 and you cannot terminate when x>2.

 

 

Answer 2

 do {
        k = (i+ j) / 2;
        if( Y[k] < x) i = k;else j = k;
    } while (Y[k] != x) && (i < j)) ;

Here i=k and j=k creates the problem.

just do i=k+1 and j=k-1

when we search the elements which is not in array and that element in the range of first and last element  results infinite looping. that is unsuccessful search and range should be inbetween first and last.

another problem when searching last element and greater than of last element.

Answer 3

Above code goes into infinite loop if element to be found is greater or equal to last element.

in option (C) we are searching for x>2 so it will go into infinite loop

Answer option (C) 

Comments

This is the correct explanation

---

good explanation

---

.

Answer 4

For binary search there are two necessary conditions:

1.Array should be sorted.

2.All the elements in the array should be distinct.

for Ques.84 option c is correct

Comments

The second one is not a requirement. It happens here just because code is wrong. See

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

---

Explanation: The above program doesn’t work for the cases where element to be searched is the last element of Y[] or greater than the last element (or maximum element) in Y[]. For such cases, program goes in an infinite loop because i is assigned value as k in all iterations, and i never becomes equal to or greater than j. So while condition never becomes false. So ans is option :C

---

@Arjun sir  why second condition is not necessary for binary search (distinct element) please explain in detail.

---

becouse if all elements same

ex. 2,2,2,2,2

and if you want to search 2 with binary search you will get in the 1 phase itself

and if you search other than the element present in the array

obiviously  you will get false simple

Answer 5

84. The answer is C.

Binary search fails if all the elements are same.

85. The answer is A.

Comments

How binary search fails when all elements are same?

---

The errorfull nature of this program is not related with "what type of elements are stored in array" .the error is regarding "what element we want to search..if the element we want to search is more than or equal to last element of array,it will cause problem as program will never terminate ..

---

If all elements are equal then searching element should be greater than the array element..in just that case it should just exactly greater..

---

No @Gate Keeda. Only necessary condition for binary search is that the input array should be sorted. In case of duplicates, the time complexity will rather decrease and it's a good thing for binary sort!