10.x — Chapter 10 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.

11.1 -- Welcome to object-oriented programming
10.16 -- Lambda captures

229 comments to 10.x — Chapter 10 comprehensive quiz

  • Rostyslav

    "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." is not from this chapter.

  • Here's my solution to Question 3. I accidentally was referring to the "array[min]", or the element, as the index parameter for "std::find"... In Virtual Studio, I was getting an "illegal indirection" error, but the code line was some random number like "7500". My buddy showed me how to identify the code line in the "build output". At the very bottom of the output, after lines and lines of information, it said "main.cpp(20)". "main.cpp" was the literal name of my .cpp file, and "(20)" is the line the compiler identified the first error in the code. Just a heads up for other noobs :)

    • Here's the build output I was referring to. See "main.cpp(20)" in the very last paragraph? That's how you find the line if the normal "error" message gives you something weird like "7540"... :)

      Build started...
      1>------ Build started: Project: 10.x Question 3, Configuration: Debug Win32 ------
      1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Professional\VC\Tools\MSVC\14.28.29333\include\xutility(5440,13): error C2100: illegal indirection
      1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Professional\VC\Tools\MSVC\14.28.29333\include\xutility(5474): message : see reference to function template instantiation '_InIt std::_Find_unchecked1<_InIt,_Ty>(_InIt,const InIt,const Ty &,std::false_type)' being compiled
      1>        with
      1>        [
      1>            _InIt=int,
      1>            _Ty=int
      1>        ]
      1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Professional\VC\Tools\MSVC\14.28.29333\include\xutility(5480): message : see reference to function template instantiation '_InIt std::_Find_unchecked<_InIt,_Ty>(const InIt,const InIt,const _Ty &)' being compiled
      1>        with
      1>        [
      1>            _InIt=int,
      1>            _Ty=int
      1>        ]
      1>C:\Users\lumit\Desktop\10.x Question 3\10.x Question 3\main.cpp(20): message : see reference to function template instantiation '_InIt std::find<int,int>(_InIt,const InIt,const Ty &)' being compiled
      1>        with
      1>        [
      1>            _InIt=int,
      1>            _Ty=int
      1>        ]
      1>Done building project "10.x Question 3.vcxproj" -- FAILED.
      ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

  • My initial take at Question 1. I know I needed to "return" the value for the 3rd function with the ability to change the element in the array's index. I got the job done here, but not that way specifically. I'll look at the solution now.

  • yeokaiwei

    1. Feedback
    The Binary Search quiz is pretty well done.

    It has a main function that comes with a checker to test whether a student's code works.

    This has a fantastic benefit of letting students just focus on what went wrong with their code.

    It would be great if all of the quizzes could check your code.

    The only issue is I can't visualize how unoptimized(lousy) my code is, even if it works.

    I would like to have a benchmark that let me know that my code is unoptimized and exactly how far off am I from the optimized version. E.g. myCode takes 999ms, while optmizedCode takes 99ms.

    Otherwise, all I know is... myCode works but I don't know if it sucks.

  • yeokaiwei

    Not optimized nor elegant compared to the answer but this was what I came up with that worked with 1 for loop.

    • nascardriver

      You're still doing it.
      Do you want to modify `mid`? No, make it `const`. When it's `const` you're forced to initialize it properly, which is what you should be doing anyway.

      • yeokaiwei

        My greatest apologies, bad habits die hard.
        I removed it for the recursive version.

        I'm a little confused for the modify 'mid' part?

        Shouldn't mid be a non-constant?

        It is constantly changing with each iteration, as max and min will change.

        • nascardriver

          `mid` dies at line 15 of your snippet. A new `mid` is created in every iteration of the loop. `mid`'s value never changes, you create a new `mid` with a different value.

          This is not bad for performance, your compiler can reuse the memory of the old `mid` so nothing is actually being created or destroyed.

          • yeokaiwei

            I'm sorry, is this what you mean?

              • yeokaiwei

                1. Thanks updated my code.

                2. Out of curiousity, can we use the Microsoft Visual Studio 2019 Performance Profiler to do comparisons? Under Debug->Performance Profiler?

                • nascardriver

                  1. `mid` is still created in each iteration, the `const` doesn't change that. I only talked about performance because that's usually the next question that comes up when people figure out that variables die at the end of each iteration.
                  The `const` is there because you have no intention of modifying `mid`. It makes the code easier to understand and prevents you from accidentally modifying `mid`.

                  2. I don't know what that is

                  • yeokaiwei

                    1. Thank goodness I clarified that. Adding the "const" does improve performance?
                    2. We'll skip Performance Profiler then.

                    • nascardriver

                      1. No, not in this case. In other cases it can allow the compiler to apply more optimizations. What improved performance for you is switching from assignment to initialization.

                      2. You can try it out, I just don't know what it is and can't help you with it.

  • yeokaiwei

    Could we have the answers for Quiz 1 in full?

    I would like to know if I got it correct.

    • nascardriver

      Quiz 1 is answered in full. The quiz only asked for prototypes.

      If you wrote full functions, feel free to share them in the comments.

  • Rishi

    Help me. My code given below doesn't work. When I run it, nothing is displayed. I can't find any errors in my code.

  • Berkeyvx

    On question 3 part b, its better if you use std::midpoint that comes with C++20. It might still overflow with that approach.

    • nascardriver

      `std::midpoint` works exactly the same as the formula used in the solution, this formula doesn't overflow. Anyway, `std::midpoint` should be used because it makes the code simpler. Thanks for the suggestion!

      • Berkeyvx

        TIL how midpoint implemented :)

        Just a reminder, if we use the formula used in the solution, we must sure that variable min have to be smaller or equal to variable max. Otherwise it might overflow. But with std::midpoint we don't have to check that.

        std::midpoint(min, max) and std::midpoint(max ,min) produce the true result.

  • Aryan

    Heres my implementation of binary search

  • Tony

    Perhaps it's just me, but the quizzes look quite hard even at this point.
    I've checked the comments and most of the solutions are very similar to yours. Mine, however, is something completely different (and in that sense, probably  a lot worse).

    If you could check this and give me some hints I'd again appreciate it a lot.

    BTW., If I don't use "midpoint+=1" or "midpoint-=1" and instead I do "max = midpoint+1" it doesn't work apparently. I don't get why, though?

    • nascardriver

      You can't use `max / 2` for `midpoint`. This is only valid if `min = 0`, but you don't know that.
      How do you know that it takes you at most 8 steps to find the element? This doesn't work for large arrays.
      `i` should be initialized with list initialization.

      You're not moving `midpoint` to the new middle of the array, so you're not performing binary search.
      Say we're searching for 2

      > BTW
      Then you're never changing the element you're comparing `target` to, ie. your loop does the same in every iteration.

      I think you didn't understand binary search. Here's a video with awful music that doesn't spoil you the code but should get you a better idea of how the algorithm works

      • Tony

        I actually got it now.

        What "confused" me is that I thought I should return array[midpoint] ONLY in case 'array[midpoint] == target' which didn't work. REmoving it and just adding an 'else' to return midpoint worked.

        I thought that the expectedValues were the actual numbers of the array - bad me for not even checking the whole main(). I realized only now what "index" had to be in the first place.... Thanks for your hints! The video helped a lot as well.

  • My implementation finding a target in std::vector, using std::binary_search to check if found, calling std::equal_range to get iterators to first (and last) elements matching the target and std::distance to calculate the index.

    • nascardriver

      You're running two binary searches (Once in `std::binary_search`, once in `std::equal_range`). You can use the result of `std::equal_range` to check if the element was found.

      • Thank you very much for the advice @nascardriver. I revised the solution adding an exit Status enumeration (distinguishing between the cases where the target value is not found because out of array range or in its range but not found) to play a bit with the iterators returned by std::equal_range. Moreover, the index is calculated simply using pointer arithmetic (without std::distance).

  • M Bratbo

    Why the else clauses? When a if clause causes a return statemen the else is unnecessary.


    Anyway this quiz shows the disadvantage of recursive solutions: assert is called multiple times when one suffices.

    • nascardriver

      Without the `else`, you have to read the body of the previous `if`-statement to know if the second one will be reached. If you use `else if`, it doesn't matter what the first `if` does, which makes the code is easier to read.

  • std::equal_range


    1) I didn't get the use case of std::equal_range.
    2) Can we use std::pair<auto,auto> instead? I tried but I got compile-time error although my compiler support std=c++20
    3) what does this statement mean ? "If there are no elements not less than value, last is returned as the first element."
    source: "

    • nascardriver

      1) `std::binary_search` doesn't return the found element, it only returns whether or not the searched element exists, because there could be more than 1 element with the searched value. If you need to know where the elements with that value are, you'll need `std::equal_range`.
      Say we have the array
      1 2 4 4 5 5 5 6 7 8
      and we search for 5
      `std::binary_search` returns `true`, but we don't know where the 5 is or how many there are
      `std::equal_range` returns an iterator to the first 5 and an iterator to the last 5. That way we know where the fives are.

      2) No, but you can use `auto` without `pair`. If your compiler supports C++20, you can use `std::ranges::equal_range` to avoid having to pass in iterators.

      3) Man that's a hard sentence. Taking out the "no"s makes it easier. "If all elements are less than value, last is returned as the first element." For example
      1 2 3 4 5
      and we search for 9. All elements are less than 9, so the first value in the returned pair is `last` (`array.end()`).

  • overflow in midpoint

    >> int midpoint{ min + ((max-min) / 2) }; // this way of calculating midpoint avoids overflow

    Can you please give me an example of overflowing if midpoint wasn't calculated in that way? I calculate midpoint in a traditional way "(min+max)/2" for a large array and no overflow happened.

    • nascardriver

      `min + max` has to be greater to `std::numeric_limits::max()` to cause an overflow.

      Use `1` for `min` and `std::numeric_limits::max()` for `max`.

  • Gowtham

    >>the array is length 9, so the index of the last element is 8
    The array length is 9 or the array is length

  • MoisturBacon

  • MoisturBacon

  • Constant_n

    My both functions look almost the same.

  • Tom

    Hi! I was wondering if in Q1 a) we should use const, since the function doesn't (and shouldn't) change the values it receives.

    • Alex

      It doesn't hurt, but it isn't necessary to make parameters passed by value const since changing them has no impact outside the function.

  • Mn3m

    Q3: Iterative...


    • 1. try stroe ((min + max) / 2) as a local variable, so that it could be calc just once.

      2. try format your code. I don't know what editor you are using. but try use some format such as 'clang-format' etc... or keep a good habbit for the indentation

      good lock

  • Suyash

    Here's my implementation of one of the simplest but in some ways, the most useful algorithm, Binary Search... Reminded me of my first algorithms class... It is one of the most important algorithms that I believe, every programmer should know... Thanks for including it on the quiz...

    a) Iterative Version

    b) Recursive Version

    One question, I saw how you calculated midpoint... In what scenario would the conventional method of finding midpoint ((a + b) / 2) would lead to an overflow?

    Referring to this line in your code:

    Will wait for your reply...

    • nascardriver


      Your algorithms look good!

      Your midpoint calculation fails whenever (min + max) > INT_MAX.
      Say the range of an `int` is [-1000, 1000] and `int` safely wraps around.

      • Suyash

        Wow, thank you for introducing techniques that could help us prevent subtle bugs from occurring in our code...

        This makes it this exercise even more valuable for everyone...

        Unfortunately, this is my last chapter for the time being (due to me being busy as my current project is nearing deployment)... I will most likely come back by mid February...

        Thank you to both you & @Alex for your wonderful contributions to this site... This site, in my humble opinion, is definitely one of the best places to learn modern C++ on the Internet...

        P.S:And, who knows, if everything goes well, I'll be back sooner...

  • Ged

    Could you give an example when it will work. Cause when I try to create an example, my compiler just throws out errors.

    • nascardriver

      If your compiler is throwing errors, you're doing something else wrong.
      `assert(array)` is successful whenever `array != nullptr`.
      What error are you getting?

      • Ged

        No I mean my program works, but I have no idea how to make my array nullptr in the example so the assert would work. Cause there is constexp. When i try to initialize it with nullptr, because it constexpr, it won't allow it, I am unable to modify it because of the const.

        The only way it can work is when I do this

        But it has no const, so my question would be do we really need assert() when we are using const?

        • nascardriver

          You won't ever get a `nullptr` when you use static arrays, but this can happen when you dynamically allocate the array.

  • Wallace

    Hi Alex and nascardriver,

    For exercise 3a, I get an error when starting from that example code:

    No matching function for call to 'binarySearch'
    1. Candidate function not viable: no known conversion from 'const int [15]' to 'int *' for 1st argument

    This is with Clang set to strict C++17 in Xcode. Adding const to the function declaration's array parameter like this solves it:

    Is there any reason the lesson's starting code doesn't have that const?

    Also, there's a minor typo early in the summary: "Most of time."

    Thanks for this great resource!

    • nascardriver

      `binarySearch`'s `array` should be `const`, thanks for pointing out the error! It worked without `const` before I made `main`'s `array` `constexpr`.
      Type fixed, thanks!

  • Hi! For quiz 3b I come with a (hopefully working) more simplified version:

  • Samira Ferdi

    Hi, Alex and Nascardriver! What do you think?

    • nascardriver


      - Initialize your variables with brace initializers.
      - Limit your lines to 80 characters in length for better readability.
      - You have `index_t`, but you're not using it everywhere.
      - Since you're using `index_t` to index the vector, `index_t` should be the same as the vector's index type. `using index_t = haystack_t::size_type;`.
      - Inconsistent formatting. Use your editor's auto-formatting feature.
      - The calls in line 23 and 26 produce the same result every time. You can use a `while (true)` loop and `break` or declare the midIndex outside of the loop.

      • Samira Ferdi

        Hi, Nascardriver! Thanks for your reply!

        So, this is my change! (full code)

        • nascardriver

          Line 61: That's a `haystack_t`.
          The rest looks good.
          Line 12 is dangerous. If the haystack is empty, the integer underflows (because -1 isn't unsigned).

          • Samira Ferdi

            Hi, Nascardriver! Thanks for replying!

            Yes, your right! Line 12 is dangerous if haystack is empty. So, I just added

            at the top in find() and binarySearchTest. But is it necessary that I have to added assertion in main() right after haytack definition?

            And I found that if find() work with vector, the while's loop expression should be:

            Deals with unsigned int is horrible pain! I understand now why other language throw out unsigned int. Do unsigned int has significant in C++, so C++ keeps using it?

            • nascardriver

              > I just added
              There's also `std::vector::empty`

              > is it necessary that I have to added assertion in main
              No. `main` has no problems if the vector is empty.

              > the while's loop expression should be
              Comparing unsigned to unsigned is fine.

              > Do unsigned int has significant in C++
              Sometimes you need that extra bit to save memory, eg. networking, or you want to represent a 32 bit rgba color, which uses up all bits but signedness doesn't make sense. And bitwise operations make more sense if all bits have the same meaning.

              • Samira Ferdi

                Hi, Nascardriver! Thanks a lot to reply my question!

                If I remove this code

                and while loop's expression is unsigned like this

                If I test this then the program is crash because maxIndex's value wrap around just to figure out 0 is exist or not!

  • hellmet

    Thank you, Alex and Nascardriver, for the great detailed tutorials, amazing quizzes and patiently clarifying the many questions I had! Really had a lot of fun along the way!
    Onwards and forwards to OOP!

  • Avijit Pandey

    Hi! Here is my attempt to the recursive version for the 3rd problem.

    I wanted to ask why you chose not to include the last condition(that the array can no longer be halved) as the base case.
    Also, please point out any mistakes that I'm not noticing.

    • - Initialize your variables with brace initializers.
      - Inconsistent formatting. Use your editor's auto-formatting feature.
      - Line 16 is always true. The way your code is now, `binarySearch` is missing a `return`-statement.
      - Line 10 could be `min >= max`. If `min == max`, then the array segment's length is 1 and you know that this last element is not the target because of line 8.

      Checking equality at the beginning is wasteful. It's unlikely that this check is true as long as the array segment's length is not 1. It's much more likely that the target is to the left or right of the mid point, so those checks should run first.

  • Anastasia

    I'm not sure whether it belongs here (sorry if it doesn't), but I wanted to put binary search in a context in order to see better how it works. So I made it play hi-lo game we've coded in chapter 5 quiz (it wins always).

    Line 69 (`int guess { ... };`) is ridiculous, is there a better way to handle/avoid those casts?

    • Hi!

      > Line 69 (`int guess { ... };`) is ridiculous, is there a better way to handle/avoid those casts?
      You don't need the cast in line 70. Your vector is a vector of int, you're casting int to int. You only need the cast for the index.

      Your entire vector is not needed. It's a contiguous list of numbers, `values[i] = (i + 1)`, you can calculate that on the fly.

      It's still a binary search if you do this, but with an imaginary list.

      • Anastasia

        > You don't need the cast in line 70. Your vector is a vector of int, you're casting int to int. You only need the cast for the index.
        I could swear my compiler kept complaining about types untill I did what I did with line 69. You're right though, I see it now.

        > Your entire vector is not needed.
        But what if I want to make it guess from a different set of numbers (say from 150 to 500)? The way I did it, I'd only need to change MIN_VALUE and MAX_VALUE respectively.

  • A

    I've checked my code against the solution several times, and can't seem to find anything wrong, yet each time I run it, it states each test value passed but the last. Am I missing something?

    • Change line 35 to

      to see what your `binarySearch` is saying. Compare the result to what you expected (Manually search 49 in the array) and what your `expectedValues` says it should be.

  • mmp52

    Hey, this might seem stupid but why didn't he use const double's when defining max Function? Aren't we supposed to use const everywhere if we don't manipulate the input?

Leave a Comment

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