CODEWITHSUNDEEP
c++arrayssearch
leslie
leslie

Reputation: 17

binary search function reuses comparison values

I have this binary search function which seems to work fine, but there's a slight issue with the final cout statement for the comparison count. The function does three runs of the binary search, with randomly generated search values each time. The comparison variable counts the amount of comparisons made for each run. Run 1 seems to output the correct amount of comparisons, but Run 2 and 3 output 0 rather than a comparison. Can anyone see the issue?

example output:

|Run 1: 
 -Search: 3980
 -Comparisons: 13

|Run 2: 
 -Search: 8538
 -Comparisons: 0

|Run 3: 
 -Search: 8844
 -Comparisons: 0

code:

void binarySearch(int nums[], int size)
{
    int first = 0;       //first array elements
    int last = size - 1; //last array
    int middle;          //midpoint of search
    int position = -1;   //position of search value
    bool found = false;  //flag

    for (int j = 1; j < 4; j++)
    {
        int comp = 0;
        int randVal = rand() % size + 1; //rand value to be searched

        while (!found && first <= last)
        {
            comp++;
            middle = (first + last) / 2; //calculate midpoint
            if (nums[middle] == randVal) //if value is at mid
            {
                found = true;
                position = middle;
            }
            else if (nums[middle] > randVal) //if value is in lower half
            {
                last = middle - 1;
            }
            else
            {
                first = middle + 1;
            } //if value is in upper ha;f
        }
        cout << "|Run " << j << ": " << endl;
        cout << " -Search: " << randVal << "\n";     //cout searched value
        cout << " -Comparisons: " << comp << "\n\n"; //cout # of comparisons that were made
    }
}

Upvotes: 0

Views: 51

Answers (2)

john
john

Reputation: 87959

The problem is that you don't reset found to false when you start a new search. So the second and third searches don't happen. The same argument applies to the other search variables first, last etc

So your code should look like this

for (int j = 1; j < 4; j++)
{
    int comp = 0;
    int randVal = rand() % size + 1; //rand value to be searched
    int first = 0;       //first array elements
    int last = size - 1; //last array
    int middle;          //midpoint of search
    int position = -1;   //position of search value
    bool found = false;  //flag  
    while (!found && first <= last)
    {
        ...

See how the variables has been moved inside the for loop, so they get set before each search, not just before the first search,

Upvotes: 1

ForceBru
ForceBru

Reputation: 44838

Your code sets found = true; here:

if( nums[middle] == randVal) //if value is at mid
{
    found = true;
    position = middle;
}

...and never resets it, so on all next iterations of the outer loop found is true, and thus the condition while (!found && first <= last) is not met, so the loop is never executed.

Yet you do reset int comp = 0; each time, so the count is going to be zero.

Upvotes: 0

Related Questions