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.

• 
  

  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.

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.

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.