3
\$\begingroup\$

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);

}
\$\endgroup\$
3
  • \$\begingroup\$ The code doesn't compile. min must be defined before it is used. \$\endgroup\$ Oct 30 '16 at 2:21
  • \$\begingroup\$ if you'll replace std::cout with printf(), you will effectively have C program. I hope you understand what I mean. \$\endgroup\$ Oct 30 '16 at 6:26
  • \$\begingroup\$ using namespace std;, using that on the code review stack exchange requires a trigger warning \$\endgroup\$ Oct 30 '16 at 11:36
4
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Nice! It would be better to take value as const T&. \$\endgroup\$ Oct 30 '16 at 14:17
  • \$\begingroup\$ Thanks for the review! I see you changed the expression in the while loop to "leftPos < rightPos" instead of leftPos != rightPos". Is there something wrong with my version of the expression ? \$\endgroup\$ Oct 30 '16 at 23:51
  • \$\begingroup\$ @SoloNasus If you pass a negative array length to your version (leftPos != rightPos), bad things will happen. (Try it.) \$\endgroup\$
    – coderodde
    Oct 31 '16 at 8:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.