Skip to main content
added 7 characters in body
Source Link
coderodde
  • 29.8k
  • 14
  • 77
  • 194
template<typename RandomIt, typename T>
RandomIt binarySearch(RandomIt begin, RandomIt end, Tconst T& value)
{
    RandomIt save_end = end;

    while (begin != end)
    {
        auto range_length = std::distance(begin, end);
        RandomIt middle = begin;
        std::advance(middle, range_length / 2);

        if (*middle == value)
        {
            return middle;
        }

        if (value < *middle)
        {
            end = middle;
            std::advance(end, - 1);
        }
        else
        {
            begin = middle;
            std::advance(begin, +1);
        }
    }

    return save_end;
}
template<typename RandomIt, typename T>
RandomIt binarySearch(RandomIt begin, RandomIt end, T value)
{
    RandomIt save_end = end;

    while (begin != end)
    {
        auto range_length = std::distance(begin, end);
        RandomIt middle = begin;
        std::advance(middle, range_length / 2);

        if (*middle == value)
        {
            return middle;
        }

        if (value < *middle)
        {
            end = middle;
            std::advance(end, - 1);
        }
        else
        {
            begin = middle;
            std::advance(begin, +1);
        }
    }

    return save_end;
}
template<typename RandomIt, typename T>
RandomIt binarySearch(RandomIt begin, RandomIt end, const T& value)
{
    RandomIt save_end = end;

    while (begin != end)
    {
        auto range_length = std::distance(begin, end);
        RandomIt middle = begin;
        std::advance(middle, range_length / 2);

        if (*middle == value)
        {
            return middle;
        }

        if (value < *middle)
        {
            end = middle;
            std::advance(end, - 1);
        }
        else
        {
            begin = middle;
            std::advance(begin, +1);
        }
    }

    return save_end;
}
Source Link
coderodde
  • 29.8k
  • 14
  • 77
  • 194

Advice 1

while(mid != leftPos)

Above, mid is not defined, so my compiler does not compile that.

Advice 2

#include<stdio.h>

I don't see your code using anything in stdio.h; why not remove it?

Advice 3

It seems that you forgot to seed the random number generator. Did you mean to

srand(time(NULL));

before creating the integer array?

Advice 4

int mid = (rightPos + leftPos)/2;

If rightPos + leftPos overflow, mid will end up negative. You can "extend the range" by writing

mid = leftPos + (rightPos - leftPos) / 2;

instead.

Putting pieces together

After a minor rewrite, your implementation may look like this:

int binSearch(int *arr, int arrSize, int num)
{
    int leftPos = 0, rightPos = arrSize - 1;

    // 'mid' not yet declared:
    int mid;

    while(leftPos < rightPos)
    {
        // Avoids overflowing '(leftPos + rightPos) / 2':
        mid = leftPos + (rightPos - leftPos) / 2;

        if(arr[mid] == num)
            return mid;
        else if(arr[mid] > num)
            rightPos = mid - 1;
        else
            leftPos = mid + 1;
    }

    return -1;
}

Alternative implementation

It is not hard to write the binary search as a template:

template<typename RandomIt, typename T>
RandomIt binarySearch(RandomIt begin, RandomIt end, T value)
{
    RandomIt save_end = end;

    while (begin != end)
    {
        auto range_length = std::distance(begin, end);
        RandomIt middle = begin;
        std::advance(middle, range_length / 2);

        if (*middle == value)
        {
            return middle;
        }

        if (value < *middle)
        {
            end = middle;
            std::advance(end, - 1);
        }
        else
        {
            begin = middle;
            std::advance(begin, +1);
        }
    }

    return save_end;
}

Hope that helps.