Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
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 #include #include using namespace std; vector make_rand_array() {     srand(time(0));     vector 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 &ar,int e) {            int lb=0,ub=ar.size(),mid;    //upper bound, lower bound, middle number of the array            for(;lbe)                ub=mid-1;            else                if(ar[mid]

And the main function, which creates the vector ar and calls the procedure to fill it with 1000000 random integers.

 c++: int main() {     vector 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!

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 else-if's single-line 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 else-if.

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 &ar, int e) {            int lb=0; // lower bound     int ub=ar.size(); // upper bound     int mid; // middle entry     for(;lb e )         {             ub=mid-1;         }         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 &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