Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   binary search question. (http://www.go4expert.com/forums/binary-search-question-t17720/)

ikj 27May2009 21:26

binary search question.
 
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!

SaswatPadhi 27May2009 22:12

Re: binary search question.
 
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: c++

#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[i] = 2*i; in the main function, so that you can test with odd numbers as target.

Sample I/O :
Code: Test-Run

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 !

ikj 28May2009 09:32

Re: binary search question.
 
thanks a million!!!:pleased:

SaswatPadhi 28May2009 09:36

Re: binary search question.
 
My pleasure :happy:


All times are GMT +5.5. The time now is 10:01.