1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

binary search question.

Discussion in 'C++' started by ikj, May 27, 2009.

  1. ikj

    ikj New Member

    Joined:
    May 14, 2009
    Messages:
    14
    Likes Received:
    0
    Trophy Points:
    0
    i know it might sound stupid asking this but im stumped.
    how could i modify the binary search code so as to find an element in the array which is just less than the element(ie wat i want t do is to find the elemnt which is anyway in the code and to find the element which is closest to it from the lesser side incase the elemnt i need is not in the array)
    here's my code:
    Code:
     
    #include<iostream>
    using namespace std;
    void bs(int a[31], int beg, int end, int x)
    {
     int mid;
     mid=(beg+end)/2;
     if(x==mid)
      cout<<"FOUND!!";
     else if(x>end)
      cout<<"NOT FOUND!!";
     else if(x<mid)
     {
      end=mid-1;
      bs(a,beg,end,x);
     }
     else  
     {
      beg=mid+1;
      bs(a,beg,end,x);
     }
    }
    main()
    {
     int a[31];
     for(int i=0;i<31;i++)
     {
      a[i]=i;
     }
     int x;
     cout<<"enter target:";
     cin>>x;
     bs(a,a[0],a[30],x);
    }
    
    thanks for reading!
     
  2. SaswatPadhi

    SaswatPadhi ~ Б0ЯИ Τ0 С0δЭ ~

    Joined:
    May 5, 2009
    Messages:
    1,343
    Likes Received:
    55
    Trophy Points:
    0
    Occupation:
    STUDENT !
    Location:
    Orissa, INDIA
    Home Page:
    Asking the above question does not sound as stupid as your code :rofl:

    Look at your bs func : the beg and end, you are working with are the values !
    You should work with index, instead.

    Correct code will be :
    Code:
    #include<iostream>
    using namespace std;
    void bs(int a[31], int beg, int end, int x)
    {
        int mid;
        mid=(beg+end)/2;
        if (x==a[mid])
            cout<<"FOUND!!\n";
        else if (x>a[end])
            cout<<"Nearest lower value found -- " << a[end] << "!!\n";
        else if (x<a[mid])
        {
            end=mid-1;
            bs(a,beg,end,x);
        }
        else
        {
            beg=mid+1;
            bs(a,beg,end,x);
        }
    }
    main()
    {
        int a[31];
        for (int i=0;i<31;i++)
        {
            a[i]=2*i;
        }
        int x;
        cout<<"enter target:";
        cin>>x;
        bs(a,0,30,x);
    }
    I have changed a = 2*i; in the main function, so that you can test with odd numbers as target.

    Sample I/O :
    Code:
    enter target:1
    Nearest lower found -- 0!!
    
    enter target:10
    FOUND!!
    
    enter target:100
    Nearest lower found -- 60!!
    
    enter target:65
    Nearest lower found -- 60!!
    
    enter target:45
    Nearest lower found -- 44!!
    
    Best of luck !
     
    Last edited: May 27, 2009
  3. ikj

    ikj New Member

    Joined:
    May 14, 2009
    Messages:
    14
    Likes Received:
    0
    Trophy Points:
    0
    thanks a million!!!:pleased:
     
  4. SaswatPadhi

    SaswatPadhi ~ Б0ЯИ Τ0 С0δЭ ~

    Joined:
    May 5, 2009
    Messages:
    1,343
    Likes Received:
    55
    Trophy Points:
    0
    Occupation:
    STUDENT !
    Location:
    Orissa, INDIA
    Home Page:
    My pleasure :happy:
     

Share This Page