binary search comparisons too high

[beastie805]

i am having difficulty with the binary search function for some reason the comparisons are coming up much higher then they should be.

heres my code from main

 comp = 0;

for( index=0; index<Max_Tests; index++)
{


    results = BinarySearch(list, test[index], comp);

    cout<< setw(5) << test[index] << setw(15); 

    if( results == -1)
    {
        cout<<"NOT Found" << endl;

    }

    else
    {
        cout<<"Found"<<setw(16)<<comp << endl;

        count_found++;

        total_comp_lin +=comp;
    }


    comp++;

}

my binary search function

int BinarySearch(const int list[], int value, int& comps)

{

    int first = 0,
        last = Max_Size-1,
        middle,
        position = -1;

    bool found = false;

    while(!found && first <= last)
    {
        middle = (first + last)/2;
        if (list[middle]== value)
        {
            found = true;
            position = middle;
        }

        else if (list[middle] > value)
            last = middle - 1;
        else
            first = middle + 1;
    }

    return position;


}

my Results

Binary Search Version
Test value    Result    Number of Comparisons
 2823          Found               0
 3056          Found               1
 1193          Found               2
 2618          Found               3
 4687          Found               4
 3151      NOT Found
 3461      NOT Found
 4786          Found               7
 3011      NOT Found
 1579          Found               9
  174          Found              10
 2569      NOT Found
 2394          Found              12
 2289          Found              13
 4119      NOT Found
 2841          Found              15
 4776      NOT Found
 1107      NOT Found
 3745          Found              18
 4671          Found              19
 4617          Found              20
  576      NOT Found
 1449      NOT Found
 1676          Found              23
 3185          Found              24
 2688          Found              25
 1232          Found              26
 3346          Found              27
 1643          Found              28
 1426      NOT Found
 1204          Found              30
 2571          Found              31
  631      NOT Found
 1001          Found              33
 1065          Found              34
 4180          Found              35
 3057          Found              36
  917      NOT Found
 3867      NOT Found
    3      NOT Found
 4475          Found              40
 2463      NOT Found
 4890      NOT Found
 2920          Found              43
 4379      NOT Found
 1261      NOT Found
 3059          Found              46
 3839          Found              47
 1725          Found              48
 2635          Found              49
Press any key to continue . . .

[beastie805]

i see its counting my all my test values and incrementing but how could i increment the actual comparisons?

[kal_crazy]

Try to utilise comps in your BinarySearch function. You're really not doing anything with that.

Comparisons in Binary Search is as such - Once a list is divided into half then the function has made a comparison and stops comparing once the value is found.

So now think about that^ and try to utilise comps in the BinarySearch function.

Hope that helps :)

[beastie805]

thanks a lot :)