The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+24 votes

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

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

+22 votes

Best answer

for Q.84

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

please explain the difference between

if (Y[k] < x) i = k + 1; else j = k-1; and

if (Y[k] < x) i = k - 1; else j = k +1;

But the same index 8 problem will also arise for option (a), when you are searching for say x=9.. Can somebody explain dat plz?

+8 votes

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.

+4 votes

+2 votes

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

1.Array should be sorted.

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

for Ques.84 option c is correct

- All categories
- General Aptitude 1.1k
- Engineering Mathematics 4.5k
- Digital Logic 1.9k
- Programming & DS 3.3k
- Algorithms 2.9k
- Theory of Computation 3.6k
- Compiler Design 1.4k
- Databases 2.7k
- CO & Architecture 2.4k
- Computer Networks 2.7k
- Non GATE 901
- Others 1.2k
- Admissions 246
- Exam Queries 433
- Tier 1 Placement Questions 17
- Job Queries 42
- Projects 4

32,330 questions

39,146 answers

108,247 comments

36,501 users