**Chapter summary**

Another chapter down! The next chapter is the best one, and you’re almost there! There’s just this pesky quiz to get past…

Function arguments can be passed by value, reference or address. Use pass by value for fundamental data types and enumerators. Use pass by (const) reference for structs, classes, or when you need the function to modify an argument. Use pass by address for passing pointers or built-in arrays.

Values can be returned by value, reference, or address. Most of time, return by value is fine, however return by reference or address can be useful when working with dynamically allocated data, structs, or classes. If returning by reference or address, remember to make sure you’re not returning something that will go out of scope.

Inline functions allow you to request that the compiler replace your function call with the function code. You should not need to use this.

Function overloading allows us to create multiple functions with the same name, so long as they have different parameters. The return value is not considered a parameter.

A default parameter is a function parameter that has a default value provided. If the caller doesn’t explicitly pass in a value for the default parameter, the default value will be used. You can have multiple parameters with default values. All parameters with default values must be to the right of non-default parameters. A parameter can only be defaulted in one location. Generally it is better to do this in the forward declaration. If there are no forward declarations, this can be done on the function definition.

Function pointers allow us to pass a function to another function. This can be useful to allow the caller to customize the behavior of a function, such as the way a list gets sorted.

Dynamic memory is allocated on the heap.

The call stack keeps track of all of the active functions (those that have been called but have not yet terminated) from the start of the program to the current point of execution. Local variables are allocated on the stack. The stack has a limited size. std::vector can be used to implement stack-like behavior.

A recursive function is a function that calls itself. All recursive functions need a termination condition.

A syntax error occurs when you write a statement that is not valid according to the grammar of the C++ language. The compiler will catch these. A semantic error occurs when a statement is syntactically valid, but does not do what the programmer intended. Two common semantic errors are logic errors, and violated assumptions. The assert statement can be used to detect violated assumptions, but has the downside of terminating your program immediately if the assertion statement is false.

Command line arguments allow users or other programs to pass data into our program at startup. Command line arguments are always C-style strings, and have to be converted to numbers if numeric values are desired.

Ellipsis allow you to pass a variable number of arguments to a function. However, ellipsis arguments suspend type checking, and do not know how many arguments were passed. It is up to the program to keep track of these details.

**Quiz time!**

1) Write function prototypes for the following cases. Use const if/when necessary.

a) A function named max() that takes two doubles and returns the larger of the two.

b) A function named swap() that swaps two integers.

c) A function named getLargestElement() that takes a dynamically allocated array of integers and returns the largest number in such a way that the caller can change the value of the element returned (don’t forget the length parameter).

2) What’s wrong with these programs?

a)

1 2 3 4 5 |
int& doSomething() { int array[] = { 1, 2, 3, 4, 5 }; return array[3]; } |

b)

1 2 3 4 |
int sumTo(int value) { return value + sumTo(value - 1); } |

c)

1 2 3 4 5 6 7 8 9 |
float divide(float x, float y) { return x / y; } double divide(float x, float y) { return x / y; } |

d)

1 2 3 4 5 6 7 8 9 10 11 |
#include <iostream> int main() { int array[100000000]; for (const auto &x: array) std::cout << x << ' '; return 0; } |

e)

1 2 3 4 5 6 7 8 9 10 |
#include <iostream> int main(int argc, char *argv[]) { int times = argv[1]; for (int count = 0; count < times; count++) std::cout << count << ' '; return 0; } |

3) The best algorithm for determining whether a value exists in a sorted array is called binary search.

Binary search works as follows:

- Look at the center element of the array (if the array has an even number of elements, round down).
- If the center element is greater than the target element, discard the top half of the array (or recurse on the bottom half)
- If the center element is less than the target element, discard the bottom half of the array (or recurse on the top half).
- If the center element equals the target element, return the index of the center element.
- If you discard the entire array without finding the target element, return a sentinel that represents “not found” (in this case, we’ll use -1, since it’s an invalid array index).

Because we can throw out half of the array with each iteration, this algorithm is very fast. Even with an array of a million elements, it only takes at most 20 iterations to determine whether a value exists in the array or not! However, it only works on sorted arrays.

Modifying an array (e.g. discarding half the elements in an array) is expensive, so typically we do not modify the array. Instead, we use two integer (min and max) to hold the indices of the minimum and maximum elements of the array that we’re interested in examining.

Let’s look at a sample of how this algorithm works, given an array { 3, 6, 7, 9, 12, 15, 18, 21, 24 }, and a target value of 7. At first, min = 0, max = 8, because we’re searching the whole array (the array is length 9, so the index of the last element is 8).

- Pass 1) We calculate the midpoint of min (0) and max (8), which is 4. Element #4 has value 12, which is larger than our target value. Because the array is sorted, we know that all elements with index equal to or greater than the midpoint (4) must be too large. So we leave min alone, and set max to 3.
- Pass 2) We calculate the midpoint of min (0) and max (3), which is 1. Element #1 has value 6, which is smaller than our target value. Because the array is sorted, we know that all elements with index equal to or lesser than the midpoint (1) must be too small. So we set min to 2, and leave max alone.
- Pass 3) We calculate the midpoint of min (2) and max (3), which is 2. Element #2 has value 7, which is our target value. So we return 2.

Given the following code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
// array is the array to search over. // target is the value we're trying to determine exists or not. // min is the index of the lower bounds of the array we're searching. // max is the index of the upper bounds of the array we're searching. // binarySearch() should return the index of the target element if the target is found, -1 otherwise int binarySearch(int *array, int target, int min, int max) { } int main() { int array[] = { 3, 6, 8, 12, 14, 17, 20, 21, 26, 32, 36, 37, 42, 44, 48 }; // We're going to test a bunch of values to see if they produce the expected results const int numTestValues = 9; // Here are the test values int testValues[numTestValues] = { 0, 3, 12, 13, 22, 26, 43, 44, 49 }; // And here are the expected results for each value int expectedValues[numTestValues] = { -1, 0, 3, -1, -1, 8, -1, 13, -1 }; // Loop through all of the test values for (int count=0; count < numTestValues; ++count) { // See if our test value is in the array int index = binarySearch(array, testValues[count], 0, 14); // If it matches our expected value, then great! if (index == expectedValues[count]) std::cout << "test value " << testValues[count] << " passed!\n"; else // otherwise, our binarySearch() function must be broken std::cout << "test value " << testValues[count] << " failed. There's something wrong with your code!\n"; } return 0; } |

3a) Write an iterative version of the binarySearch function.

Hint: You can safely say the target element doesn’t exist when the min index is greater than the max index.

3b) Write a recursive version of the binarySearch function.

8.1 -- Welcome to object-oriented programming |

Index |

7.14 -- Ellipsis (and why to avoid them) |

Why is max from

and min from

not equal to midpoint? Why is it midpoint - 1 and midpoint + 1 respectively? Does it have something to do with the fact that the array starts at 0?

In each iteration, we test to see whether the midpoint is greater than, less than, or equal to our target value. If the midpoint is NOT our target value, then we can search on half of the remaining array in the next iteration. Since we have already determined that the midpoint is not our target number, we don’t need to include the midpoint itself in the next iteration. The -1 and +1 are so we don’t include the midpoint itself in the next iteration.

Wow, I did not think about that. Thank you! 🙂

I did in a messy way but it worked.

can anyone tell me why the below function is not working

while this works

Take 13 in testValues[] as an example, and do it on the paper step by step.

You will reach a point when min = 3 and max = 4, which correspond to 12 and 14 in array[], so in the next iteration, the midpoint now is 3, and the target is still greater than array[midpoint]. However, your code call binarySearch() again, with your min = midpoint, which actually does nothing change (both are 3), so you end up with infinite number of function calls to binarySearch() with all their min = 3.

Hey Alex,

In your solution for 3a, you had:

Can you explain, I do not quite understand what you meant. How is it better than:

For sake of example, let’s say the range of an integer is -9 to 9. Now consider what happens when min = 6 and max = 8. Clearly the midpoint should be 7, right?

It’s pretty easy to see that int midpoint = (min + max) / 2 overflows in this case. min + max = 14, which is outside the range of our integer. So instead of 14, this will be evaluated as some negative integer, like -6. -6 / 2 = -3, which is the wrong answer.

min + ((max - min) / 2) evaluates as: 6 + ((8 - 6) / 2), which is 6 + 1 = 7. No overflow. When you think about this logically, it’s pretty easy to understand why: In this calculation, we start at min, and then we add half the distance between min and max. We know max is within range, so min + half the distance to max must be within range too (as this number must be less than or equal to max).

Thanks. When you said overflow, I somehow thought the index would be out of bounds. Nice cat

For 1 a), I came up with

In fact, I find myself using const whenever I know that the parameter should be read-only within the function. Is this approach incorrect? Advantages? Disadvantages?

No, use of const is good practice, and should be encouraged. There’s no disadvantage to doing so, and the advantages are that you know right away whether the function can modify the parameter. Also, in the case of reference parameters, you can do a lot more with a const reference than a non-const reference (like pass in a literal or anonymous value).

I have something that is bothering me..

With:

By default the midpoint will always be lower than the actual middle of the array? Which was okay if the array was even ("if the array has an even number of elements, round down")

But if the array has an uneven amount of numbers? Wont the integer division round it down? i.e. int 15 / int 2 = 7 (rounded from 7,5), when it should be 8 instead?

Does this differ from each compiler or is this intented?

By the knowledge we have up until this point shouldnt the correct way be:

Side question: Is it better to calculate max - min once and store it minMaxRange or is it better to not save it in a variable and calculate it twice?

I’m loving your tutorial by the way!!

Thanks

Integer division always drops any fractional components (a result of 8.2, 8.5, and 8.99 will all become 8).

In the case where the array has an even number of elements (array indexes 0-7), the midpoint is actually between elements 3 and 4. The goal of binary search is to discard as many elements each iteration as possible -- picking as close to the midpoint as we can get each time allows us to do this. In the case where the midpoint is between elements, it actually doesn’t matter whether we round up or down -- either way we’ll be able to discard the same number of elements each iteration. Since rounding down is easier, we just do that.

For something as simple as max - min, where max and min are integers, I’d just calculate it twice. This makes the code more straightforward (by reducing the number of variables), which is what you should be optimizing for.

Less variables gives more straightforward code. Got it.

Thanks for your answer!

> Less variables gives more straightforward code

Not always… Every variable you create adds some amount of complexity to your code. But judicious use of variables can reduce complexity by allowing you to simplify other statements.

Just ask yourself: does using a variable here add more complexity (by introducing another variable) than it reduces (by simplifying other statements)? If so, don’t do it. If the reduction in complexity is greater, than do it. If it’s about the same, then it probably doesn’t matter.

That makes sense! 🙂

Hi Alex,

Thanks for your tutorials, they are the first with which I dare to undertake learning c++ (coming from python) Looking forward to Chapter 8.

One small thing, I think your algorithm for ‘binarySearch’ can fail with large arrays. I used your earlier ‘bubbleSort’ to make a big array of size 1000 or more, and made ‘target’ always array[some_index], so it MUST be found. On some occasions, the rounding of integers in midpoint

work together to just skip the target value. When I changed the line

it worked flawlessly, as far as I could test.

Keep up the good work!

EDIT:

My apologies! I just noticed that my algorithm is slightly different than yours. Within the while-loop, the order of checks is different than yours, which made it go off sometimes.

I just retested the code with arrays of size 999 and 1000 and was able to find all elements as expected. I’m not sure what you mean by “work together to just skip the target value”. First, do you agree that which specific element we pick for the midpoint doesn’t really matter? We pick as close to the midpoint as possible because it allows us to discard the most elements per iteration, but we could pick any other point and the algorithm would still work (just less efficiently). Second, if array[midpoint] > target, then we don’t need to recheck the midpoint element again in a future iteration (we know it doesn’t match), so we can set max to midpoint - 1.

It is worth noting that the algorithm does assume the elements in the array are sorted and unique. If either of these are not true, then you may get unexpected results.

First, I agree with you that your algo works fine as it is, as I said in my EDIT comment.

So, as to why my particular algo only works with "end = curIdx", I can only guess. After careful examination I found another small difference. Your condition in the while loop is ‘>=’, mine was only ‘>’, so it bails out earlier. This probably explains the difference.

Second, the elements in the array were sorted, but not unique. However, in such case binarySearch might find the adjacent element, which is identical, but won’t return "not found".

regards,

Hermen

Right, if the array has duplicate elements, the binary search algorithm will always correctly identify whether the elements exists or not, but it may return the index of any of those elements (depending on what other elements are in the array).

Problem with recursive binary search solution:

I was struggling with how the recursive binary search program returns the correct index value as it exits the recursions. Came across this strange outcome and wondering why.

I added some std::cout statements to track what was going on. The following code executes correctly:

Producing the following output (using the first 3 test values):

However, if I un-comment the last std::cout statement just before the function exits (to track how the recursive calls ‘unwind’)

I get the following output:

As you can see, adding the std::cout statement at the end of the function results in returning a garbage value for the function. This is what I was expecting before I added the statement at the end - what value does the initial entry into the function return when it is the last one popped off the stack? It’s only the last call to the function that has a return value, how does it percolate back through all the other calls to come out at the end? The multiple earlier calls never execute a return. Do they ‘inherit’ a return from the recursive function calls?

My only guess is that by adding the statement at the very end, the compiler inserts an assumed return statement after it - but what does it return? Obviously a garbage value! But why not when there isn’t a statement there and it just ‘falls out’ of the function?

If you don’t supply a return value for a function that returns a non-void value, in most cases, the compiler will catch this and error out. But in some more complicated cases, the compiler can’t tell if you’ve returned a value for every case, and it won’t catch a missing return value. That’s what’s happening here. In these cases, there is no implied return value. What gets returned is indeterminate, depending on how the compiler sets up the stack.

In your first case, it just happens to work. But as soon as you do something as simple as introduce some output statements, that indeterminate-ness ends up breaking your program. That’s the nature of indeterminate results.

Thanks. I see now where my problem was. Instead of calling a new version of binarySearch recursively, I should return the call of the recursion.

Now there are no paths that can fall out the bottom of the function with no defined return values. The final returned value then gets passed back as the return value for each level of the recursion.

Makes my head hurt sometime trying to figure out the paths of these recursions.

Alex, I believe it’s a typo:

"If the caller doesn’t not explicitly pass in a value for the default parameter, the default value will be used." -> "does not" or just "doesn’t".

Regards.

Mauricio

Yup, typo. Fixed now, thanks!

More than welcome!

Yes, I meant a dynamic array. I’ve used one here with recursion to compare. However it only executes successfully if I put 10k or less as the arraySize. Anything more e.g. 100K, program crashes with a program not working message box. What is my error? Its using the heap right? - Thx Alex R.g.

Addendum: works fine with http://cpp.sh/

Is it my console?

Should I also reference the pointer being passed (n_ptr) as well?

Your function foo() is calling itself for each element in the array, leading to recursion. Remember, the function stack is stored on the stack, not the heap. You’re running out of stack memory somewhere between 10000 and 100000 nested functions due to the recursion.

I thought “new” ultimately ended on the heap. However, its on the stack as you pointed out. Why does this occur?

The new keyword dynamically memory on the heap. The problem with your program isn’t the array allocation, it’s the recursion of function foo, which is stored on the stack.

Alex thx for answering all of my questions. Fantastic site, learn so much. I’ve been through a few and this one is 1.serious 2.thorough.

The pay sites should be afraid of you! On to chpt 8!

Hi Alex I wanted to confirm your statement: "…even with an array of a million elements, it only takes at most 20 iterations to determine whether a value exists in the array or not! However, it only works on sorted arrays…".

The program below confirmed your findings. Using a binary search to find a value in a million ordered elements usually results in 18-20 recursions (iterations), 20 being most common! You can put in high numbers for range e.g. 200,000,000 with a target value search, 27 recursions in this case. Comment out printArray

if using large numbers.

Question(s): which would perform a binary search faster: pointers or vectors? Does vector copy natively or as above does it require & to not copy as with pointers? How large of an array can you fit on the stack? This example is self evident for heap.

> Question(s): which would perform a binary search faster: pointers or vectors?

By pointers, I presume you actually mean dynamic arrays. The speed between the two should be comparable so long as you’re not making unnecessary copies of things.

> Does vector copy natively or as above does it require & to not copy as with pointers?

You should always pass std::vector by reference, otherwise it’ll make a copy.

> How large of an array can you fit on the stack?

Depends on the size of your stack and how much other stuff you’re putting on the stack.

The binary search is essentially the same thing as a binary root search on a (mathematical) function, except in the example above we are finding an exact target in an array, rather than an approximation to a root. Just thinking out loud.

Hello dear Alex, I constantly read your tutorial over a few months now, it’s awesome, thank you 🙂

Although I found some errors, and I want to give my input to improve your tutorials,

if you care, then I will send any errors I faced as I go through your tutorial.

I really enjoy!!!

The error I found on this particular quiz:

if (array[midpoint] > target)

{

return binarySearch(array, target, min, midpoint - 1);

}

else if (array[midpoint] < target)

{

return binarySearch(array, target, midpoint + 1, max);

}

else

return midpoint;

I think this is a semantic error and

I believe we should swap the

return binarySearch(array, target, min, midpoint - 1);

and

return binarySearch(array, target, midpoint + 1, max);

places!

The binary search function here is designed to work with arrays that have been sorted in ascending order. Your suggestion would work with arrays that have been sorted in descending order. Using function pointers you could replace the conditionals with function calls to make different comparisons based on the array passed in.

I completely understand that it is designed to work with arrays sorted in ascending order. I still believe I am right. Please review the logic again, @Darren.

I don’t think I agree. If the array is sorted in ascending order, and the midpoint value in the array is greater than our target number, that means the target value (if it exists) must exist in the lower half of the array (from min to midpoint-1).

Okay, here’s my logic, we are looking for value 7

{1, 2, 3, 4, 5, 6, 7, 8, 9}

min=0 max=8 (midValue=5 doesn’t fit)

continue looking, midValue is smaller than 7,

so we look in the upper.. (oops you are right, sorry my bad @Darren, @Alex)

{1, 2, 3, 4, 5, 6, 7, 8, 9}

min=5 max=8

But still I think it is better to use an array with different values in the example, cause it also works when I swap the statements in the recursive solution, that could lead to misunderstanding in the future as in my particular situation

Alex, per problem #c what exactly do you mean by this; its not clear to me from the wording (seems vague). The rest of the algorithm is done.

>>in such a way that the caller can change the element

Updated question to: “c) A function named getLargestElement() that takes a dynamically allocated array of integers and returns the largest number in such a way that the caller can change the value of the element returned”

Is that clearer?

Yes. Greatly appreciated.

OOP HYPE

isn’t this one from the previous lessons better than the answer in quiz 1. b) ?

Maybe only if you want to preserve the original values as well. Typically swap functions only take two parameters though, and swap the values.

oh ok … but to swap the values they would need to declare two temporary variables to hold the original values right ?

int function ( x = 3 , y = 6 )

x = y; // 6

y = x; // 6

You’d only need one temporary value. If the inputs are x and y, you can do this:

temp = x;

x = y;

y = temp;

oh yeah didn’t realize that thanks.

Hey Alex, nice summary and quiz once again to wind up the chapter. Enjoyed it.

I’d like to point out that the note after the solution to question 1c makes it a bit too easy. I believe you intended it to be inside the solution, but it somehow got outside. Is that so?

Thanks once again. Looking forward to the next chapter! 🙂

Indeed. Fixed!

Pssst… Alex, you left the answer visible in 2c, before the code block:

c) Two functions that only differ by return type.

Which made working out the solution rather easy, I must say 😉

(Also- Thank you ever so much for these tutorials! I’ve learned more in the few weeks I’ve been following these than I did in two /years/ of programming back in school: they’re beautifully written and you’ve done a great job of presenting a complex subject so that it looks simple.)

Hah, whoops. Fixed. Thanks for pointing that out. And thanks for visiting!

Hey Alex,

In my implementation I statically declared the midpoint variable,

thinking that this would prevent midpoint from being instantiated on each recursion. Is my thinking correct?

Yes, but this actually doesn’t save anything. All local variables are set up as part of the stack frame when the function is entered, so there’s no (or minimal) cost to instantiating them. The cost is in the initialization.

Using a static makes sense if the initializer is a constant, because then you only need to do an initialization once. Using static does not make sense if the initializer is not constant, as in the case above.

I think the answer to Question 3c has the same overflow problem. Assuming int is 16-bit, if min=-32768 and max=32767 then overflow will still occur. Alternately, assuming min is always >= 0 could easily lead to a violated assumption.

I’ve updated the solution to one that I don’t think will overflow for any valid min and max values.

Yes, but that won’t find the correct midpoint in the case where min and max are odd… I suspect a better result would need to use static_cast twice (to double, and then back to int)?

Yeah, you’re right. I’ve reverted back to the previous solution. In this case, overflow could still occur if min is less than 0, but since that’s an invalid element index, the we’ll only run into issues if the user starts passing invalid values. And if they do that, the fact that we’re overflowing isn’t really going to matter, our code isn’t going to work as expected anyway.

A better solution would be to guard against this case separately.

The following gives compiler error:

‘return’: cannot convert from ‘const int’ to ‘int &’

The first parameter mustn’t be const. So answer to 1c appears to be wrong, or there is a way I cannot see.

Yep, mistake on my part. I removed the const from parameter array.

Is this wrong ? sorry for the too many questions , thank’s thank’s thank’s

I think so, it’ll just be slightly less efficient since you’re not excluding the midpoint you just checked with each iteration.

thank’s for the awesome summery and quiz but shouldn’t this:

be like this :

tell if I’m wrong please

Yes! Thanks for the correction.

Alex,

How to perform binary search with std::array and std::vector.

The same way we did it in the quiz example.

array array has 15 members and the call to binarySearch implies 16 members.

Good catch! I’ve fixed the code.

Not an expert, but I think neither of the 3a, nor 3b binary search examples are binary searches. Doesn’t a binary search split a sorted list into smaller and smaller parts? The examples given just scan inwards from the ends.

Okay, may be wrong about that, I’ll have to think about it some more. >_<

No, the example start in the middle and then cut off half of the remaining array with each pass.

Alex, in the code for quiz 3 (binary search test framework), line 23, I believe, should read

instead of

Also, in the line 28, I think you meant expectedValues[count] instead of expectedIndices[count].

Thanks for the notes! These have now been fixed in the article.