11.x — Chapter 11 comprehensive quiz

Quick 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 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. Make your pass by reference and address parameters const whenever possible.

Values can be returned by value, reference, or address. Most of the 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 the inline keyword because the compiler will generally determine this for you.

Function overloading allows us to create multiple functions with the same name, so long as each function is distinct in the number or types of parameters. The return value is not considered when determining whether an overload is distinct.

A default argument is a default value provided for a function parameter. If the caller doesn’t explicitly pass in an argument for a parameter with a default value, 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.

Lambda functions are functions that can be nested inside other functions. They don’t need a name and are very useful in combination with the algorithms library.

Quiz time

Question #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.

Show Solution

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

Show Solution

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

Show Solution

Question #2

What’s wrong with these programs?


Show Solution


Show Solution


Show Solution


Show Solution


Show Solution

Question #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:

a) 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.

Show Solution

b) Write a recursive version of the binarySearch function.

Show Solution


std::binary_search returns true if a value exists in a sorted list.
std::equal_range returns the iterators to the first and last element with a given value.

Don’t use these functions to solve the quiz, but use them in the future if you need a binary search.

12.1 -- Welcome to object-oriented programming
11.14 -- Lambda captures

241 comments to 11.x — Chapter 11 comprehensive quiz

  • Szymon :)


    Can someone explain how is this way of calculating midpoint vulnerable to overflow?

    And how does way avoid the overflow?

    • Szymon :)

      Also a side quesion: I can't seem to find any way to delete or edit my comment (withing an hour of posting it, I actually tried right after).
      Where is the delete/ edit button located?

  • Haldhar Patel

    I have a silly doubt:

    I was wondering , what if we put continue inside the if and else if statements , will it increase the overall performance by skipping the next statements or their is no effect.

    • Alex

      It should not have any positive impact. Once an if/else branch is selected, there is no need for the others to be evaluated.

      This is also potentially dangerous, as if you later add a new statement below the if/else branches it won't execute since continue will skip it.

  • Kap

    I didn't like the idea of the min exceeding the max so I implemented a way to conclude the recursion by checking if the max and min happen to be equal. It's a bit inefficient but I'm wondering if there are any glaring mistakes?

    Also what do you mean by "prevents overflow" when referring to how to find the midpoint. What is wrong with (min + max)/2 ?

  • Sparkly

    I've looked this over and am over all pretty stumped. I implemented binary search using what I thought was the right idea (recursion, which felt like the expected solution), but I'm not asking whether or not my solution was right, but what makes this program not do anything when I run it.

    basically this program won't output anything at all, I think it's crashing when I run it, no compile errors though, anyways If you can see anything immediately wrong with my code please tell me. The only thing I changed outside of binarySearch was in main where std::size was called, I couldn't get C++ to recognize it so I just replaced it with 14.

    Edit: I'm sorry, I must be using the code tag wrong somehow? It worked until I edited the comment and now it's just plain text. Sorry for the inconvenience.

    • Maxy

      I'm not sure but your midpoint calculation is also incorrect, it will divide min first and then add it to max, you might need to add braces

  • Bigom

    ... and I was just about to comment to ask you about

    Because mid will always be min and you have to check that condition too, to recurse the function down further. I didn't realize that

    You can remove that midpoint too and it becomes way easier.
    Thank you for the chapter. I learned a lot, especially about that confusing closure concept.

  • Rayyan Khan

    Aced this quiz!

  • yeokaiwei

    Hi Alex,
    Silly newbie question.

    Is a quicksort algorithm = binary search?

        Always pick first element as pivot.
        Always pick last element as pivot (implemented below)
        Pick a random element as pivot.
        Pick median as pivot.

Leave a Comment

Put all code inside code tags: [code]your code here[/code]