Binary Search in C++17

Question

Question

Any way I can optimize this further with C++11 or C++17 features?

Would also like feedback on my variable naming, memory management, edge case handling (in this someone calling my function with an nullptr or int overflow with my rearranged equation to calculate the mid), and coding style. If there are other data structures I can use to implement this instead of basic arrays and raw pointers I'd like some feedback there too.

For my return type on the binary_search function, does it matter if I return a bool versus an int?

Code

#include <cassert>
#include <iostream>

bool binary_search(int* data, int num_elements, int target)
{
    int low = 0;
    int high = num_elements - 1;
    int mid;

    if(data == nullptr) { throw std::exception(); }

    while(low <= high) {
        mid = low + (high - low) / 2;
        if(data[mid] == target) {
            return 1;
        } else if(data[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return 0;
}

int main()
{
    int num_elements = 6;

    int data[] = { 5, 8, 10, 15, 26, 30 };
    int target[] = { 5, 4, 12, 15, 35, 30 };
    int expected[] = { 1, 0, 0, 1, 0, 1 };

    for(int i=0; i < num_elements; ++i) {
        try {
            assert(expected[i] == binary_search(data, num_elements, target[i]));
            std::cout << expected[i] << " returned for search on " << target[i] << '\n';
        } catch(std::exception& e) {
            std::cout << "Exception " << e.what() << '\n';
        }
    }

    return 0;
}

Answer 1

• An idiomatic approach

  to implement this instead of basic arrays and raw pointers

  is to use iterators.

• Returning bool is dubious. The situation where I only want to know if the element is present or not is very rare. Typically I want to know where exactly the element is (or, if absent, where it should be inserted to keep the collection sorted). Your function does compute this information, but immediately throws it away. Return an iterator.

• All that said, consider the signature

  template<typename It, typename T>
  It binary_search(It first, It last, const T& target)
  

  It is now suspiciously similar to the standard library's std::lower_bound. Follow the link for further insight and inspiration.

Answer 2

Considering you are using the same numbers as their example, I assume you're already aware of the binary search algorithm.

• Regarding coding style I prefer a space between flow control statements and the parenthesis but that is purely subjective.

• Don't compare to nullptr. Do if (!data) instead.

• IMO Not much use in printing out what() if you don't provide (meaningful) messages along with your exception.
  Could also specialize it.
  e.g.: std::invalid_argument("no input provided").

• Could use brace initialization if you want to use more modern C++ features (nitpick: mid is not initialized).

• Why didn't you use vector? It's pretty much a drop-in replacment. You could then also use the range for loop.

• return 0 is implicit in main.

Answer 3

In the if/else statement, I would put the most frequently true conditions at the top to reduce the amount of condition checking. Is it really more common for data[mid] to equal target than for it to be greater than or less than it? I doubt it, so I'd reorder the blocks to something like:

if (data[mid] > target) {
    high = mid - 1;
} else if(data[mid] < target) {
    low = mid + 1;
} else {
    return true;
}

You could also reduce hard coding by replacing num_elements with std::size(data).

Returning true or false is more readable than returning 1 or 0. It expresses the function's purpose more clearly and avoids confusion.

Finally, replacing the division by 2 with a bit shift might not help but it's worth testing if this is performance-critical:

mid = low + ((high - low) >> 1); // ">> 1" is "/ 2"

EDIT: On Clang, bit shifting actually does help (GCC gives the optimization either way), but you can get the same benefit by appending a u to the 2, which is more readable anyway. 2u is unsigned, so it causes (high - low) to also be cast to unsigned, which tells Clang that it's never negative (which GCC already deduced from your while condition) and that a bit shift is therefore safe to do on it. You can also simplify the arithmetic a little since you're just calculating an average. These two tweaks reduce the assembly for this line to just 2 instructions (down from 7 on Clang or 4 on GCC):

mid = (high + low) / 2u;