8
\$\begingroup\$

As before, I am moving into C++ and would like to learn about its idioms. I have moved from Project Euler to CodeKata as the former is based on algorithms, rather than language constructs (as suggested by bruglesco in the comments).

Description (slightly modified):

Write a binary search method that takes an integer search target and a sorted array of integers. It should return the integer index of the target in the array, or -1 if the target is not in the array.

main.cpp:

#include <assert.h>
#include <math.h>
#include <iostream>
#include <vector>

int binarySearch(int needle, std::vector<int> values);
unsigned int middleOf(int leftBound, int rightBound);
void testBinarySearch();


int main() {
    testBinarySearch();
    return 0;
}


int binarySearch(int needle, std::vector<int> values) {
    constexpr int NOT_FOUND = -1;

    const unsigned int length = values.size();

    // If empty, needle will never be found
    if (length == 0) {
        return NOT_FOUND;
    }

    // Bracket the needle with [leftBound, rightBound]
    unsigned int leftBound = 0;
    unsigned int rightBound = length - 1;

    // Start at middle of bracket
    // If even number of entries, use the one on the left
    unsigned int position = middleOf(leftBound, rightBound);

    // Binary search ends in at most ceil of log base 2 of length + 1
    const unsigned int maxIterations = ceil(log(length) / log(2)) + 1;

    int value;
    for (unsigned int iteration = 0; iteration < maxIterations; ++iteration) {
        value = values.at(position);

        if (value == needle) {
            return position;
        } else if (value < needle) {
            leftBound = position;
            rightBound = rightBound;
            position = position + middleOf(leftBound, rightBound);
        } else if (value > needle) {
            leftBound = leftBound;
            rightBound = position;
            position = position - middleOf(leftBound, rightBound);
        }
    }

    return NOT_FOUND;
}


unsigned int middleOf(int leftBound, int rightBound) {
    return (rightBound - leftBound + 1) / 2;
}


// Test cases given on website
void testBinarySearch() {
    std::vector<int> values;
    assert(-1 == binarySearch(3, values));

    values.push_back(1);
    assert(-1 == binarySearch(3, values));
    assert( 0 == binarySearch(1, values));

    values.push_back(3);
    values.push_back(5);
    assert( 0 == binarySearch(1, values));
    assert( 1 == binarySearch(3, values));
    assert( 2 == binarySearch(5, values));
    assert(-1 == binarySearch(0, values));
    assert(-1 == binarySearch(2, values));
    assert(-1 == binarySearch(4, values));
    assert(-1 == binarySearch(6, values));

    values.push_back(7);
    assert( 0 == binarySearch(1, values));
    assert( 1 == binarySearch(3, values));
    assert( 2 == binarySearch(5, values));
    assert( 3 == binarySearch(7, values));
    assert(-1 == binarySearch(0, values));
    assert(-1 == binarySearch(2, values));
    assert(-1 == binarySearch(4, values));
    assert(-1 == binarySearch(6, values));
    assert(-1 == binarySearch(8, values));

    std::cout << "All tests passed!";
}

I will add files to GitLab here and make changes to them as I receive feedback.

| improve this question | | | | |
\$\endgroup\$
  • \$\begingroup\$ The problem statement itself goes against the normal C++ idioms, so I wonder about its suitability for the stated purpose. You would implement something with the same kind of API as the std::binary_search, std::equal_range, etc. functions, returning an iterator rather than an index, and working on any kind of container. \$\endgroup\$ – JDługosz Jun 23 '18 at 9:26
9
\$\begingroup\$
  • There is no need to pass values by value (pun not intended). Prefer passing it by constant reference:

    int binarySearch(int needle, const std::vector<int>& values)
    
  • An idiomatic C++ would not pass the vector at all, but a pair of iterators (first and last). It immediately increases the usability of your code, because it becomes applicable to any random access container (e.g. std::array, C-style array, etc).

    A little bit more work (invoking std::distance) would make your code applicable to many more containers.

  • unsigned int may not be wide enough to hold std::vector.size(). Use std::vector::size_type, or at least size_t.

  • Declare variables is as narrow scope as possible. value is only uses inside the loop, and shall be declared there:

        int value = values.at(position);
    
  • Most algorithms are expressed more naturally on the semi-open intervals, that is where the right bound does not belong to the range. At least, there would be no need for unintuitive + 1 in middleOf.

  • leftBound = leftBound and rightBound = rightBound definitely raises some eyebrows. Don't do that.

  • middleOf does not compute the middle of left and right. Instead it returns a half-baked result, which the caller has to use in further computations. Prefer returning the real middle:

    size_t middleOf(size_t left, size_t right) {
        return left + (right - left)/2;
    }
    

    Among other things, that would streamline the loop:

    {
        size_t middle = middleOf(left, right);
        if (values[middle] == needle) {
           return value;
        }
        if (values[middle] < needle) {
            right = middle;
        } else {
            left = middle + 1;
        }
    }
    
  • Using log might indeed lead to the correct result, but it (a) complicates the analysis, and (b) is totally unnecessary. A natural condition to terminate the loop is leftBound >= rightBound.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ the original middleOf(..) actually returns something which can be completely out of the search range: e.g. with leftBound=99 and rightBound=100, the original middleOf() will return 1. \$\endgroup\$ – Andre Holzner Jun 23 '18 at 17:48
  • \$\begingroup\$ By "[pass] a pair of iterators", do you mean pass use std::vector<int>::iterator iterator; iterator = myVector.begin(); and myVector.end();? \$\endgroup\$ – FromTheStackAndBack Jun 24 '18 at 4:52
4
\$\begingroup\$

Honestly, there's nothing wrong with this code. It's quite good how it is. There are a few minor things you could add, but if this came by me in a code review at work, I probably wouldn't have much to say. So here's what I can say:

Use const for Things that Won't Change

You're already using constexpr for the constant in binarySearch(), but you also aren't going to modify either the needle or values. I would make them const to show the intent of their use in the function. I would also make values a const reference because it could potentially be copied and if it's large, that will be slow.

Do All the Calculation in a Function

Your middleOf() function is named as if it should calculate the middle of the range that's passed to it. But it doesn't. You need to add position to the result returned from middleOf(). You should simply return the right value so the called doesn't need to add anything to it. I would define it like this:

unsigned int middleOf(const position, const int leftBound, const int rightBound) {
    return position + (rightBound - leftBound + 1) / 2;
}

Then it can be called like this:

position = middleOf(position, leftBound, rightBound);

You could also declare it constexpr.

Naming

Overall your naming is pretty good. However, the meaning of the name needle is unclear. Is it a "needle in a haystack"? If so that's a bit of a stretch. I'd just name it something clear like toFind or searchValue.

| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ Just a note: needle is a pretty classic name for this kind of algorithm that you'll find in a lot of algorithm books. Not that there's any reason to not go with a more explicit name, but hey traditions are something ;) \$\endgroup\$ – Voo Jun 23 '18 at 10:12
  • \$\begingroup\$ It's true that middleOf is badly named. But your proposed method introduces a serious bug since you get wrong results in case of overflows. The correct solution for fixed size integers is to use a + (b - a) / 2 assuming a <= b which is guaranteed here (well ok it'd be the correct solution for a half open interval, throw in the +1 if you want to make the code more complicated by using closed intervals). \$\endgroup\$ – Voo Jun 23 '18 at 10:28
  • \$\begingroup\$ D'oh! Yep, I see what you're saying about middleOf(). Fair point. In that case, they should pass in the position, left and right. I'll update it. As for needle, I've not heard that before (been programming professionally for 30 years), but it seems rather culturally specific. \$\endgroup\$ – user1118321 Jun 23 '18 at 16:03
  • \$\begingroup\$ Yeah I actually checked TAoCP and CLRS and neither uses needle in their section. So yeah, I'm certain that I've heard it in the past, but I couldn't even give you a source - so yeah, not that great a name :-) (Don't feel bad about the overflow bug though, that one was in a lot of production quality libraries - i.e. Java had it for much over a decade without anybody noticing..) \$\endgroup\$ – Voo Jun 23 '18 at 17:37
3
\$\begingroup\$

Instead of having to forward-declare the functions, put main at the bottom and generally define earlier in the file than use.

constexpr int NOT_FOUND = -1;

This is inside the function, so the callers of the function cannot make use of it. The use of -1 is exposed anyway.

⧺Enum.5 Don't use ALL_CAPS for enumerators and ⧺ES.9 Avoid ALL_CAPS names.

good (up to date best practice) for using constexpr instead of static const here.

int binarySearch(int needle, std::vector<int> values) {

Someone already pointed out that you are duplicating the vector for no reason.

const unsigned int length = values.size();

Good to remember the unchanging value rather than calling the function over and over, but don’t assume you know what type it is. It is actually size_t, which is platform specific. Use auto when declaring things, or look up the proper type to use.

const unsigned int maxIterations = ceil(log(length) / log(2)) + 1;

You do not need this! The loop will end when the high and low index positions meet or cross. I’ve never heard of an implementation that does this.

int value;
  ⋮
    value = values.at(position);

Declare the variable where you need it, not outside the loop.

unsigned int middleOf(int leftBound, int rightBound) {
    return (rightBound - leftBound + 1) / 2;
}

That doesn’t make sense.

unsigned int position = middleOf(leftBound, rightBound);

In this first use, you are assuming that leftBound is zero.

You should return the index between the two provided indexes. You are returning half the size of the interval, which is not the "middle".

assert(-1 == binarySearch(3, values));

Your test cases will not run in a release build! assert is a debug-only thing. Suggest you look into Catch2.


I’ve thought about binary searching myself, recently. The classic logic taught in school is slow on a modern architecture because the if is essentially random, thus never predicted correctly.

I think a more efficient function would compute both possible new values (mid+1 and mid-1) and then use conditional moves to update the bounds. No else, as only one of them will be triggered.

Looking at your code, you set

        leftBound = position;

or

        rightBound = position;

when you know for sure that position is in fact out of range. Normally, this would be called mid and you set the updated left to mid-1, or right to mid+1.

| improve this answer | | | | |
\$\endgroup\$

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.