somebody help me analyse?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

+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

+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

+2

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.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.8k
- Algorithms 3.3k
- Theory of Computation 4.1k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1.1k
- Others 1.4k
- Admissions 498
- Exam Queries 443
- Tier 1 Placement Questions 19
- Job Queries 60
- Projects 9

37,183 questions

44,756 answers

127,494 comments

43,817 users