9
\$\begingroup\$

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;
}
\$\endgroup\$
  • 4
    \$\begingroup\$ That depends. What are you optimizing for? Runtime? CPU cycles? Memory usage? Minimal (or maximal) chance of attracting the attention of demonic entities from the 12th dimension? ??? \$\endgroup\$ – Bob Jarvis May 26 at 13:29
  • 1
    \$\begingroup\$ I want to optimize for runtime, great point I should call this out more explicitly in future posts... well if those entities produce this stardewvalleywiki.com/Void_Essence. Yes.Yes I do want to attract them. \$\endgroup\$ – greg May 26 at 16:33
  • 1
    \$\begingroup\$ You could optimize it by using a standard algorithm: std::lower_bound() \$\endgroup\$ – Martin York May 30 at 19:33
15
\$\begingroup\$
  • 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.

\$\endgroup\$
  • \$\begingroup\$ Very very similar, now I pretty much have an implementation just as the same as binary_find from the std::lower_bound docs you linked. \$\endgroup\$ – greg May 25 at 17:58
  • \$\begingroup\$ Also for binary_find from the std::lower_bound docs, is the Compare template even needed, I suspected it may not be, removed it in my implementation and the code appears to run the same as expected? Is this compare equivalent to my while(low <= high)? \$\endgroup\$ – greg May 25 at 18:14
  • 1
    \$\begingroup\$ @greg By default, std::lower_bound and its companions use operator< to do comparisons. The compare template allows the caller to change the comparison function (for example if the data you're searching doesn't overload operator<). \$\endgroup\$ – Kyle May 26 at 1:13
  • 2
    \$\begingroup\$ Isn't OP's algorithm a std::binary_search? I don't see this is a lower bound. \$\endgroup\$ – Rakete1111 May 26 at 6:28
  • 3
    \$\begingroup\$ @greg lower bound returns the first element that is greater than target; your algorithm searches for an exact match. \$\endgroup\$ – Rakete1111 May 26 at 13:33
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Is brace initialization preferred and why? Is this not an example of brace initialization int data[] = { 5, 8, 10, 15, 26, 30 };? I debated on initializing mid to 0, any negative implication to not initializing it? To optimize I will switch to vector I had no strong reason behind using an array. \$\endgroup\$ – greg May 25 at 18:04
  • \$\begingroup\$ How should he avoid leaving mid uninitialized on declaration? A bit more meat please. Brace-initialization? Whatever… and it's the wrong term. std::vector where a raw array works? No, even if the compiler could in theory optimize it all away. Also, it is perfectly for-range compatible. \$\endgroup\$ – Deduplicator May 25 at 19:51
  • 1
    \$\begingroup\$ Technically, nullptr does not necessarily have to be equal to 0, it is OS specific. So, I don't know if it's a good idea to use !data instead of comparing to nullptr \$\endgroup\$ – glaba May 26 at 6:10
  • \$\begingroup\$ @glaba Interesting, can you provide examples where that is the case? \$\endgroup\$ – yuri May 26 at 6:31
  • \$\begingroup\$ @glaba if(!data) is equivalent to if (data == nullptr), see Can I use if (pointer) instead of if (pointer != NULL)?. \$\endgroup\$ – ComFreek May 26 at 12:24
4
\$\begingroup\$

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;
\$\endgroup\$
  • 3
    \$\begingroup\$ I’m afraid I have to differ on bit shifting instead of division. This is not necessarily faster, and it reduces readability significantly. See stackoverflow.com/q/6357038/9716597. \$\endgroup\$ – L. F. May 26 at 3:20
  • 1
    \$\begingroup\$ @L.F., I just de-emphasized that part and added a comment to help the readability of the bit shift. It very well might not help but it's easy enough to test. If this is performance critical, which I assume it is (why use a binary search otherwise?), it's worth testing, IMO, since the division is happening in a loop within a loop. \$\endgroup\$ – Gumby The Green May 26 at 4:10
  • 1
    \$\begingroup\$ I will eat my hat if you put the division by 2 into godbolt.org and don't get exactly the same assembly as a bit shift with -O2. \$\endgroup\$ – Yet Another User May 26 at 6:12
  • 3
    \$\begingroup\$ @CarstenS, in this case, the dev has info that the compiler might not - that the dividend is always non-negative - so communicating that to the compiler somehow can help it optimize. It looks like simply appending a u to the 2 in the OP's code also works, so that's probably the most readable way to do it. I'll add it to the answer. \$\endgroup\$ – Gumby The Green May 26 at 10:38
  • 1
    \$\begingroup\$ Note that the expression (high + low) may overflow. \$\endgroup\$ – Carsten S May 26 at 13:26

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.