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

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:1Nearest lower found -- 0!!enter target:10FOUND!!enter target:100Nearest lower found -- 60!!enter target:65Nearest lower found -- 60!!enter target:45Nearest lower found -- 44!!`

Best of luck !

 ikj 28May2009 09:32

Re: binary search question.