1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

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