GATE CSE
First time here? Checkout the FAQ!
x
+8 votes
679 views

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 ") ;
 }

The correction needed in the program to make it work properly is 

  1. Change line 6 to: if (Y[k] < x) i = k + 1; else j = k-1; 
  2. Change line 6 to: if (Y[k] < x) i = k - 1; else j = k +1; 
  3. Change line 6 to: if (Y[k] < x) i = k; else j = k;
  4. Change line 7 to: } while ((Y[k] == x) && (i < j)) ;
asked in Algorithms by Veteran (92.5k points) 972 2329 3115
edited by | 679 views
Given progeam is errorneous bcz it is doing malfunction when we are serching for an element that not present in the array.

I.e. 10 20 30 40 50 60 70 80 90 100

Now search 65 it will go into infinite loop

And that problem occured due to improper index (i,j) updation.

and the correct updation is Option A which is followed by Binary Search.

2 Answers

+10 votes
Best answer

Ans should be A

if( Y[k] < x) then i = k + 1;

if given element that  we are searching is greater then searching will be continued upper half of array

otherwise j = k - 1;

lower half.

Take few case in consideration i.e.

1. all elements are same

2. increasing order with no repeatation

3. increasing order with  repeatation.

answered by Veteran (39k points) 25 107 343
selected by
manoj could u explain a bit more

@asu ... see .. suppose our array is - 1, 2, 3, 4,  5, 6

and we want to search x=7, then check what happens here-

In the beginning , i=0, and j=5.

k= (0 + 5)/2 = 2.

A[2] <7, so  i=k=2.


now while (A[2] != x&& i <j) - true

2nd time - i=2, j=5.

k= (2+5)/2= 3

A[3] < 7, so i=k=3


while(A[3] !=x && i<j) - true

3rd time - i=3, j=5.

k= (3+5)/2= 4.

A[4] < 7, so i= k=4.


while(A[4] !=x && i<j) - true

3rd time - i=4, j=5.

k= (4+5)/2= 4.

A[4] < 7, so i= k=4.


while(A[4] !=x && i<j) - true

3rd time - i=4, j=5.

k= (4+5)/2= 4.

A[4] < 7, so i= k=4.

.

.

.

 will go into infinite loop.

So to get rid of this infinite loop if we put- i = k+1. instead of i=k then it would not fall into infinite loop.

..

.and you can put j= k-1 and even j=k is also okay. 

 

.

 

@vijay...thank u for explaniation ....but to check each option it will take much time..any suggestion for these kind of question

Sorry @asu .. I am also working on it  ... but I think .. while reading BST .or any topic... if we consider every cases and especially edge case then we can solve most of the question related to any topic .. smiley

 

Is there any case in which::  if we update i=k+1 and keep j=k , then the given program will give erroneous answer??

As far as I understood. I think even i=k+1 and j=k will work fine.

but if we change

do{

}while(Y[k] !=x && i<=j)

then j=k-1 is necessary.

Correct me if I am wrong !!!

@VS

I think it will work fine for even j=k, no need to change to j=k-1
+4 votes
Just try to search Last element : it will go into infinite loop because of interger division.

i=k+1 will solve the problem.

lets elemets are : 10 20 30 40 50 60 70 80 90 100

now try to search 25 or 35 or 45 or 55 on above array so it will run into infinite loop.

so we need both the conditions=i=k+1 and j=k-1

P.S: This program is errorenous because of unsuccessful search.
answered by Veteran (25.3k points) 13 60 193
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23398 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8280 Points

  4. srestha

    6300 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4352 Points

  9. sushmita

    3970 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Popular Question sh!va
Popular Question sh!va
Regular Rishabh Gupta 2
Popular Question Sunil8860
Reader Rajesh Veeranki 2
Notable Question rahul sharma 5
Commentator Shivam Chauhan
Notable Question set2018
Nice Comment srestha
Notable Question set2018
27,325 questions
35,177 answers
84,123 comments
33,280 users