#include <iostream>

int binary_search(int arr[], int size, int target)
{
    int first = 0;
    int last = size - 1; 
    int midpoint = (last   first) / 2;
    
    while(first <= last)
    {
        if(arr[midpoint] == target)
        {
            return midpoint;
        }
        else if(arr[midpoint] < target)
        {
            first = midpoint   1;
        }
        else if(arr[midpoint] > target)
        {
            last = midpoint - 1;
            
        }
    }
    
    return 0;
}

int main()
{
    int arr[] = {4, 12, 23, 43, 50, 60, 230, 290};
    int size = sizeof(arr)/sizeof(arr[0]);
    int target = 12;
    std::cout << binary_search(arr, size, target);
}

if the midpoint value is lesser than the target it increases 'first' and if it's greater than the target it instead decreases 'last'. This continues until 'first' is equal to 'last'. I saw another program where they called the function recursively but i wanted to make it work without it, what exactly am i doing wrong?

CodePudding user response：

You basically forgot to update midpoint in each iteration. An updated version of your code here (not using those "C" style arrays).It was also not clear if you meant to return the found value or the index at which it was found.

#include <iostream>
#include <vector>

auto binary_search(const std::vector<int>& values, int value)
{
    std::size_t first = 0;
    std::size_t last = values.size() - 1; // use vector it keeps track of its size
    
    while (first <= last)
    {
        std::size_t midpoint  = (last   first) / 2; // you forgot to update midpoint each loop

        if (values[midpoint] == value)
        {
            return values[midpoint]; // <== do you want to return the position or the value?
        }
        
        if (values[midpoint] < value)
        {
            first = midpoint   1;
        }
        else if (values[midpoint] > value)
        {
            last = midpoint - 1;
        }
    }

    return 0;
}

int main()
{
    std::vector<int> values{ 4, 12, 23, 43, 50, 60, 230, 290 };
    std::cout << binary_search(values, 12);
    return 0;
}

CodePudding user response：

You always access the same value of the array arr[midpoint]

while(first <= last)
{
    if(arr[midpoint] == target)
    {
        return midpoint;
    }
    else if(arr[midpoint] < target)
    {
        first = midpoint   1;
    }
    else if(arr[midpoint] > target)
    {
        last = midpoint - 1;
        
    }
}

Because you never update the value of midpoint so the conditions of your if statements will always give the same result

CodePudding user response：

you wrote mid = (high low)/2 outside while loop