2
\$\begingroup\$

I am trying to write a binary search algorithm to work with any data type that is defined to work with the relational operators and returns the position of the found element. I want to know if there is anything I need to be aware of when dealing with user defined types. As well as any flaws or improvements that I can make. Also one other question is how does my search compare to the built in binary_search function?

#include <iostream>
#include <iomanip>
#include <type_traits>

template<typename T, typename U>
U BinarySearch(T *arr, T toFind, U _size){ //make return type same as size for overflow issues
    static_assert(std::is_integral<U>::value, "Integral type required for size of array");

    U mid, low = 0, high = _size-1; //maintain same integral types
    T m, l = arr[low], h = arr[high]; //maintain same T types

    while(l<=toFind && h>=toFind){
        mid = (high + low)/2;
        m = arr[mid];
        if(m > toFind){
            h = arr[high = mid - 1];
        }
        else if(m < toFind){
            l = arr[low = mid + 1];
        }
        else
            return mid; //postion point + 1
    }

    //exits if not found
    return -1;
}

const auto SIZE = 10;

int main()
{
    double arr[SIZE] = {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.1};
    auto pos = BinarySearch(arr, 1.1, SIZE);
    std::cout << pos << '\n';
    return 0;
}

Thanks for all your advice in advance.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ It would be much better to write iterator based find. Very rarely things are just pointers to some memory. \$\endgroup\$ Oct 20, 2017 at 15:36
  • \$\begingroup\$ @Incomputable Will it be faster or safer or something like that? I want this to work with classes as well. \$\endgroup\$ Oct 20, 2017 at 15:38
  • \$\begingroup\$ It will be clearer, and more compatible with other things. I'd use user defined types rather than classes, as it is the standard terminology \$\endgroup\$ Oct 20, 2017 at 15:39
  • \$\begingroup\$ I made sure to use that terminology in the question. Could you elaborate on compatibility and such? @Incomputable \$\endgroup\$ Oct 20, 2017 at 15:40
  • 1
    \$\begingroup\$ @NickPavini I see. Still, that question makes no sense anyhow. Your sort does not inherently perform better or worse than an iterator based approach. It's just that an iterator based approach is much more flexible with regards to what it can sort. \$\endgroup\$ Oct 20, 2017 at 16:02

1 Answer 1

2
\$\begingroup\$

Apart from the fact that you should prefer writing algorithms to work with iterators (to enable you to sort things that aren't arrays, such as std::lists), there are a few things here that are problematic:

  1. Don't make assumptions about the signedness of your U type, which seems to represent the size type of the array. Oftentimes, U will be unsigned (e.g. because it is std::size_t), which means returning -1 on not finding a value might be unexpected behaviour for your users.

  2. Check that _size is greater than zero. If it is not, your program invokes undefined behaviour.

  3. Take toFind by const reference since you don't know which type it will be, whether it will be trivially copyable and so on and so forth. The same is true for m, l and h; you should either make them pointers to elements in the array or make them store the index to their respective elements instead.

  4. Be careful with overflow. In particular, (high + low)/2; may overflow the passed size type and you may end up getting nowhere. Instead, divide them separately and add the results together.


These are the pitfalls and dangers I spotted. There is a lot more to say about your code, however, but I will leave this to somebody else.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you. I did not think about compatibility with lists or the unsigned type I was passing in. Much appreciated \$\endgroup\$ Oct 20, 2017 at 16:07
  • \$\begingroup\$ @NickPavini I think the most important point is the excissive copying. Especially if T is expensive to copy. You should remove m, l and h from your code and pass toFind by const reference. \$\endgroup\$ Oct 20, 2017 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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