Binary Search
Author 
Message 
saltpro15

Posted: Thu Jan 13, 2011 12:44 pm Post subject: Binary Search 


Implementing A Binary Search in C++
Hello all! This is my first post on here in a while, so I thought I'd show a simple way to implement the Binary Search Algorithm. There are many practical applications for binary searches (eg Google) due to the fact that they work by halving the number of elements in the array during each iteration, making them very efficient.
Before the search is implemented, we need an array for it to search! I wrote up a quick function to generate a vector of 1000000 random integers to be searched.
c++: 
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector <int> make_rand_array() {
srand(time(0));
vector <int> N;
for (int i = 0; i < 1000000; i++)
{
int i = rand() % 10000 + 1;
N.push_back(i);
}
sort(N.begin(),N.end());
return N;
}

Now we can get to the search! I used a function that takes an array of integers (which we generated) and an int e (the element being searched for) as parameters. We search from the lower bound of the array to the upper bound, halving the array each iteration. We then check the middle number of the array. If the middle number is the number we're searching for, the search is complete! Otherwise, we check if the middle number of the array is higher or lower than the number we're searching for, and adjust the upper or lower band accordingly.
c++: 
void Search(vector <int> &ar,int e)
{
int lb=0,ub=ar.size(),mid; //upper bound, lower bound, middle number of the array
for(;lb<ub;)
{
mid=(lb+ub)/2;
if(ar[mid]==e)
{
cout<< "Element found.\n";
break;
}
else
if(ar[mid]>e)
ub=mid1;
else
if(ar[mid]<e)
lb=mid+1;
}
if(ub<lb)
cout<<"Element not found.\n";
}

And the main function, which creates the vector ar and calls the procedure to fill it with 1000000 random integers.
c++: 
int main()
{
vector <int> ar;
ar = make_rand_array();
int e;
printf("Please enter the element to be found\n");
scanf("%d", &e);
Search(ar,e);
getchar();
getchar();
return 0;
}

I hope this tutorial helped you understand the Binary Search Algorithm. Feel free to suggest any additions or ways to make this tutorial clearer! 





Sponsor Sponsor



Tony

Posted: Thu Jan 13, 2011 12:52 pm Post subject: RE:Binary Search 


It should be emphasized that the numbers in the array are in a sorted order. 
Tony's programming blog. DWITE  a programming contest. 




saltpro15

Posted: Thu Jan 13, 2011 12:53 pm Post subject: RE:Binary Search 


D'oh! >.< Thanks Tony, I trust you'll make the edit? I don't think I can edit it once it's been commented on 





Tony

Posted: Thu Jan 13, 2011 1:21 pm Post subject: RE:Binary Search 


That rule should only apply to the Turing Help forum. Let me know if it's otherwise and you can't make edits here. 
Tony's programming blog. DWITE  a programming contest. 




DemonWasp

Posted: Thu Jan 13, 2011 1:26 pm Post subject: RE:Binary Search 


Not a bad tutorial, but there are three things I see as problems:
1) Search should return a value of some kind, probably a boolean: true if the element is found, false otherwise.
2) Your if(){} in Search is a disaster. It's not wrong, it's just poorly written. Mixing the if's block {} with the elseif's singleline both looks horrible and is difficult to read. Worse, putting the "if" part of "else if" on the next line and indented makes it look like the preceding "else" is just an else, not an elseif.
3) Your comment mixes up the order of upper bound, lower bound and middle.
The code would be neater written as:
code: 
bool search ( vector <int> &ar, int e)
{
int lb=0; // lower bound
int ub=ar.size(); // upper bound
int mid; // middle entry
for(;lb<ub;)
{
mid=(lb+ub)/2;
if(ar[mid]==e)
{
return true;
}
else if ( ar[mid] > e )
{
ub=mid1;
}
else if ( ar[mid] < e )
{
lb=mid+1;
}
}
// Note: no check needed here;
// if we fall out of the above loop,
// we know that either lb > ub,
// or lb == ub and ar[lb] != e, so
// the entry was not found.
return false;
}







md

Posted: Thu Jan 13, 2011 9:01 pm Post subject: Re: RE:Binary Search 


Better yet, return the index where the value was found or 1 if it wasn't found. Also, why initialize variables outside the loop when that's what the initialization section is for?
c++: 
int search ( vector <int> &ar, int e)
{
for(int lb = 0, int ub = ar.size(), int mid = (lb+ub)/2; lb < ub; mid=(lb+ub)/2) {
if( ar[mid] == e )
return mid;
else if( ar[mid] > e )
ub = mid  1;
else if( ar[mid] < e )
lb = mid + 1;
}
return 1;
}







Tony

Posted: Thu Jan 13, 2011 9:21 pm Post subject: RE:Binary Search 


Also the last "else if" can be replaced with an "else". 
Tony's programming blog. DWITE  a programming contest. 




saltpro15

Posted: Fri Jan 14, 2011 1:54 pm Post subject: RE:Binary Search 


I can't make edits, good suggestions though, I wrote this in about 10 minutes so if a mod could add these suggestions that would be great 





Sponsor Sponsor




