Binary Search

[saltpro15]

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=mid-1;            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!

[Tony]

It should be emphasized that the numbers in the array are in a sorted order.

[saltpro15]

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]

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

[DemonWasp]

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 <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=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]

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]

Also the last "else if" can be replaced with an "else".

[saltpro15]

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