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,342
    Likes Received:
    55
    Trophy Points:
    0
    Occupation:
    STUDENT !
    Location:
    Orissa, INDIA
    Home Page:
    http://www.crackingforfun.blogspot.com
    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,342
    Likes Received:
    55
    Trophy Points:
    0
    Occupation:
    STUDENT !
    Location:
    Orissa, INDIA
    Home Page:
    http://www.crackingforfun.blogspot.com
    My pleasure :happy:
     

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice