**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.

3c) Extra credit: What’s wrong with this code, and how could it be improved?

1 |
int midpoint = (min + max) / 2; |

8.1 -- Welcome to object-oriented programming |

Index |

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

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.

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.

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

Good catch! I’ve fixed the code.

Alex,

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

The same way we did it in the quiz example.

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.

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.

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.

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.

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.

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, 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!

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.

OOP HYPE

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.

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

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.

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.

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!

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!