binary search on vectors

[arjita07]

i have written code which performs recusive binary search on vector,please tell y the program is not giving correct output...

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
using namespace std;
vector<int> a;
int bin_search(vector<int> a,int,int,int); 
void rand(int);
int main()
{
	int n,x;
	vector <int>::iterator it;

	cout<<"\n enter no of elements: ";
	cin>>n;
	rand(n);
	cout<<"\nARRAY IS: ";
	it=a.begin();
while(it!=a.end())
	{	
	cout<<*it<<" ";
		it++;
	}

	sort(a.begin(),a.end());

	cout<<"\nSORTED ARRAY IS: ";

	it=a.begin();
while(it!=a.end())
	{	
		cout<<*it<<" ";
		it++;
	}
	cout<<"\n enter element to be searched: ";cin>>x;
	  int pos=bin_search(a,0,n,x);
	  if(pos>=0) cout<<"\n element found at position : "<<pos;
	  return 0;

}
void rand(int n)
{
	int x;
	for(int i=0;i<n;i++)
	{		x=rand()%(n*2);
cout<<" "<<x;
		a.push_back(x);
	}
}
int bin_search(vector<int> a,int l,int u,int k)
{ 
	if(l>u) 
	{
		cout<<"\n SEARCH NOT POSSIBLE"; return -1;
	}
	if(l==u)
	{
		if(a.at(l)==k)
			return l+1;
		else
			cout<<"\n UNSUCESSFULL SEARCH";
		return -1;
	}
	else
	{
		int m=(l+u)/2;
		if(a.at(m)==k) return m+1;	
		if(a.at(m)>k)
			bin_search(a,l,m-1,k);
		else
			bin_search(a,m+1,u,k);
	}

}

[Texan40]

I really don't know what you mean by "binary search". Your bin_search() function doesn't make any sense to me. I compiled and ran it and this was the output:

 enter no of elements: 4
 1 3 6 4
ARRAY IS: 1 3 6 4
SORTED ARRAY IS: 1 3 4 6
 enter element to be searched: 6

 element found at position : 2293340

If you are just searching the vector for a specific value why not just:

int bin_search(vector<int> &a, int num)
{
  for(int idx = 0; idx < a.size(); ++idx)
    if(a.at(idx) == num)
      return ++idx;
  return -1;
}

EDIT: made change to bin_search() function as above and re-ran with this output:

 enter no of elements: 10
 1 7 14 0 9 4 18 18 2 4
ARRAY IS: 1 7 14 0 9 4 18 18 2 4
SORTED ARRAY IS: 0 1 2 4 4 7 9 14 18 18
 enter element to be searched: 7

 element found at position : 6

[arjita07]

i am suppose to reduce complexity.... nd the problem is
Implement a user defined recursive procedure to perform binary search. Use pre-defined STL sort function to ensure a sorted sequence is passed as input to the recursive binary search procedure. Comment upon asymptotic analysis of binary search implemented as above.

[arjita07]

i made these two code :

this one is working perfectly fine...
(using array)

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
void sort(int ar[],int i,int j)
{
	int s=ar[i],pos,f=0;
	for(int k=i;k<j;k++)
	{		
		if(ar[k]<s)
		{
			s=ar[k];
			pos=k;
			f=1;
		}
		if(f)
		{
			ar[pos]=ar[i];
			ar[i]=s;
		}
		f=0;
	}
	if(i==j)
		return;
	else
		sort(ar,++i,j);
}
int bin_search(int a[],int l,int u,int k)
{
        if(l>u)
        {
               cout<<"\n SEARCH NOT POSSIBLE"; return -1;
        }
        if(l==u)
        {
                if(a[l]==k)
                        return l+1;
                else
                        cout<<"\n UNSUCESSFULL SEARCH";
                return -1;
        }
        else
        {
                int m=(l+u)/2;
                if(a[m]==k) return m+1;
                if(a[m]>k)
                        bin_search(a,l,m-1,k);
                else
                        bin_search(a,m+1,u,k);
        }

}
int main()
{
	int ch,a[80],n;
			cout<<"\n ENTER NUMBER OF ELEMENTS IN ARRAY: ";
				cin>>n;
				cout<<"\n ENTER ARRAY ELEMENTS: \n";
				for(int i=0;i<n;i++) cin>>a[i];
sort(a,0,n);
cout<<"\n sorted array: ";
				for(int i=0;i<n;i++) cout<<a[i]<<" "; 
			
				cout<<"\n ENTER ELEMENT TO BE SEARCHED: ";
				cin>>ch;
				ch=bin_search(a,0,n-1,ch);
				if(ch!=-1) cout<<"\n ELEMENT FOUND AT: "<<ch;
	

	return 0;
}

on similar line i made STL code...
this one is not giving desired output..

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
vector<int> a;
int bin_search(vector<int> a,int,int,int); 

int main()
{
	int n,x;
	vector <int>::iterator it;

	cout<<"\n enter no of elements: ";
	cin>>n;
cout<<"\n enter elements: ";
for(int i=0;i<n;i++)
{
 cin>>x;
a.push_back(x);
}
	cout<<"\nARRAY IS: ";
	it=a.begin();
	while(it!=a.end())
	{	
		cout<<*it<<" ";
		it++;
	}

	sort(a.begin(),a.end());

	cout<<"\nSORTED ARRAY IS: ";

	it=a.begin();
	while(it!=a.end())
	{	
		cout<<*it<<" ";
		it++;
	}
	cout<<"\n enter element to be searched: ";cin>>x;
	int pos=bin_search(a,0,n-1,x);
	if(pos>=0) cout<<"\n element found at position : "<<pos;
	return 0;

}
int bin_search(vector<int> a,int l,int u,int k)
{ 
	if(l>u) 
	{
		cout<<"\n SEARCH NOT POSSIBLE"; return -1;
	}
	if(l==u)
	{
		if(a.at(l)==k)
			return l+1;
		else
			cout<<"\n UNSUCESSFULL SEARCH";
		return -1;
	}
	else
	{
		int m=(l+u)/2;
		if(a.at(m)==k) return m+1;	
		if(a.at(m)>k)
			bin_search(a,l,m-1,k);
		else
			bin_search(a,m+1,u,k);
	}

}

please someone explain me the reason for these different o/p... one working fine and other not.... please help
thanks in advance...