binar search function not returning # of comparisons-CodePudding

Given an integer and a sorted array of integers, write a binary search function named binary_search that prints the number of comparisons performed doing a binary search. The function should take 3 arguments:

the number searched for,
the array of integers, and
the number of elements in the array.

If the number searched for is not in the array then the function should return the maximum number of searches to determine the element is not in the array.

Here is an example call to the function:

#include <iostream>
    
using namespace std;
    
//Function for binary_search
int binary_search(int search_value, int lst[], int elements)
{
    //Dividing the array elements to its half
    int mid = elements / 2;
        
    //Condition to check search value is less then list of mid element and return it.
    if (lst[mid] > search_value)
        return binary_search( elements,lst, mid);
    //Condition to check search value is greater then list of mid element and return it.    
    else if (lst[mid] < search_value)
        return binary_search( search_value,&lst[mid], (elements   1)/2);
    else
        return mid;
}

int main()
{
    int lst[] = {0, 1, 2, 18, 19, 20, 25}; 
    std:cout << binary_search(20, lst, 7);
}

When I search for 20 it returns the index it is found, which is 5, instead of the number of comparisons, which should be 2.

CodePudding user response：

There are a few problems with your code. First off this line:

return binary_search( elements,lst, mid);

Since your first argument is the number you are searching for, it should always be the same, search_value.

Then, the idea behind a binary search is that the number of elements is halved with each call, so you don't need to change your third argument at any point, it always is elements/2 1.

Finally, as mentioned in the comments, your function doesn't return the number of comparisons but rather the number "mid". Since each call does a single comparison, you essentially have to find the number of calls. So, your base case for recursion (when you find the number you are searching for) should return 1, since to find it you have done a comparison. Then you just return 1 the number of recursive calls already made.

In the end the code should look like this,

int binary_search(int search_value, int lst[], int elements)
{
    int mid = elements / 2;
    
    if (lst[mid] > search_value)
            return 1   binary_search( search_value, lst, elements/2   1);
 
    else if (lst[mid] < search_value)
            return 1   binary_search( search_value, &lst[mid], elements/2   1);

    else
            return 1;
}

CodePudding user response：

I would propose the solution below:

[Demo]

#include <iostream>  // cout

//Function for binary_search
int binary_search(int search_value, int lst[], int elements)
{
    //Base case: not found
    if (elements == 0) { return 1; }

    //Dividing the array elements to its half
    int mid = elements / 2;
    
    //Condition to check search value is less then list of mid element and return it.
    if (lst[mid] > search_value)
    {
        return 2   binary_search(search_value, lst, mid);
    }
    //Condition to check search value is greater then list of mid element and return it.    
    else if (lst[mid] < search_value)
    {
        return 3   binary_search(search_value, &lst[mid   1], elements - mid - 1);
    }
    else
    {
        return 3;
    }
}

int main()
{
    int lst[] = {0, 1, 2, 18, 19, 20, 25};
    std::cout << "lst: ";
    for (auto&& i : lst)
    {
        std::cout << i << " ";
    }
    std::cout << "\n";
    for (auto&& i : lst)
    {
        std::cout << "binary_search(" << i << ", lst, 7): "
                  << binary_search(i, lst, 7) << "\n";
    }
    std::cout << "binary_search(10, lst, 7): "
              << binary_search(10, lst, 7) << "\n";
}

// Outputs:
//
//   lst: 0 1 2 18 19 20 25 
//   binary_search(0, lst, 7): 7
//   binary_search(1, lst, 7): 5
//   binary_search(2, lst, 7): 8
//   binary_search(18, lst, 7): 3
//   binary_search(19, lst, 7): 8
//   binary_search(20, lst, 7): 6
//   binary_search(25, lst, 7): 9
//   binary_search(10, lst, 7): 9

Explanation:

We add a base case for calls to binary_search with 0 elements. This is a safety case for calls with 0 elements, but also a base case during recursive calls when an element is not found. Since we are doing a comparison, we return 1.

if (elements == 0) { return 1; }

For values smaller than the pivot element, lst[mid], we do 2 comparisons (== 0, > search_value) plus the ones returned by the recursive call.

//Condition to check search value is less then list of mid element and return it.
if (lst[mid] > search_value)
{
    return 2   binary_search(search_value, lst, mid);
}

For values bigger than the pivot element, we do 3 comparisons (== 0, > search_value, < search_value) plus the ones returned by the recursive call.

//Condition to check search value is greater then list of mid element and return it.    
else if (lst[mid] < search_value)
{
    return 3   binary_search(search_value, &lst[mid   1], elements - mid - 1);
}

Otherwise, the value is equal to the pivot element, and we return 3 comparisons (== 0, > search_value, < search_value). This is the second base case.

else
{
    return 3;
}