Binary search in C++ I was wondering if I have any hidden bugs or traps in my code I wrote for an exercise.

#include&lt;iostream&gt;
#include&lt;stdlib.h&gt;
#include&lt;stdio.h&gt;
#include&lt;time.h&gt;
#include&lt;algorithm&gt;
using namespace std;

# define MAX 1000

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

    while(mid != leftPos)
    {
        int mid = (rightPos + leftPos)/2;
        if(arr[mid] == num)
            return mid;
        else if(arr[mid] &gt; num)
            rightPos = mid;
        else
            leftPos = mid;
    }

    return -1;
}

int main(){

    /*testing program */
    int arr[MAX];
    for(int i = 0; i &lt; MAX; i++)
        arr[i]=rand()%100;

    sort(arr, arr+MAX);

    cout&lt;&lt;binSearch(arr, MAX, 4);

}
Advice 1

while(mid != leftPos)


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

Advice 2  

#include&lt;stdio.h&gt;


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 &lt; rightPos)
    {
        // Avoids overflowing '(leftPos + rightPos) / 2':
        mid = leftPos + (rightPos - leftPos) / 2;

        if(arr[mid] == num)
            return mid;
        else if(arr[mid] &gt; 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&lt;typename RandomIt, typename T&gt;
RandomIt binarySearch(RandomIt begin, RandomIt end, const T&amp; 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 &lt; *middle)
        {
            end = middle;
            std::advance(end, - 1);
        }
        else
        {
            begin = middle;
            std::advance(begin, +1);
        }
    }

    return save_end;
}


Hope that helps.