somebody help me analyse?

The Gateway to Computer Science Excellence

+30 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

+32 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

0

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;

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

0

As I solved for option D, with $$x=10$$, the code seems to go in infinite loop. So option D is also incorrect. Please correct me if I am wrong.

0

for x = 10 in option D, it will find k = (0 + 9)/2 = 4 and Y[4] = 10. the while loop will exit, giving you the answer. There is no infinite loop in that.

0

https://gateoverflow.in/2770/gate1996-18 is this question same .what is the difference between these two?

0

@arjun sir

but same problelm arises with option b if x=0 which is not present then we will no get any result.then b and c both should be wrong.why we are only seeing c option?

but same problelm arises with option b if x=0 which is not present then we will no get any result.then b and c both should be wrong.why we are only seeing c option?

+12 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

+3 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

+3

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,313 answers

198,349 comments

105,052 users