-----------------------------------

saltpro15

Thu Jan 13, 2011 12:44 pm


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 
#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.


void Search(vector  &ar,int e)
{       
    int lb=0,ub=ar.size(),mid;    //upper bound, lower bound, middle number of the array       
    for(;lb ub,
    // or lb == ub and ar[lb] != e, so
    // the entry was not found.
    return false;
} 
[/code]


-----------------------------------

md

Thu Jan 13, 2011 9:01 pm


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?


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


-----------------------------------

Tony

Thu Jan 13, 2011 9:21 pm


RE:Binary Search

-----------------------------------

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


-----------------------------------

saltpro15

Fri Jan 14, 2011 1:54 pm


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 :D