Binary search in C++

Question

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

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<algorithm>
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] > num)
            rightPos = mid;
        else
            leftPos = mid;
    }

    return -1;
}

int main(){

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

    sort(arr, arr+MAX);

    cout<<binSearch(arr, MAX, 4);

}

Answer 1

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, 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;
}

Hope that helps.