Search

7.x — Chapter 7 comprehensive quiz

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.

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

2) What’s wrong with these programs?

a)

Show Solution

b)

Show Solution

c)

Show Solution

d)

Show Solution

e)

Show Solution

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:

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.

Show Solution

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

Show Solution

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

Show Solution

8.1 -- Welcome to object-oriented programming
Index
7.14 -- Ellipsis (and why to avoid them)

51 comments to 7.x — Chapter 7 comprehensive quiz

  • Mike

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

  • May

    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.

  • Makar

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

  • yash

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

  • Mekacher Anis

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

    be like this :

    tell if I’m wrong please

  • Mekacher Anis

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

  • Mustafa

    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.

  • ozdmc

    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.

    • Alex

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

      • ozdmc

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

        • Alex

          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.

  • SJ

    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?

    • Alex

      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.

  • Charamei

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

  • Shiva

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

  • J3ANP3T3R

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

  • Rob G.

    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

    • Alex

      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?

  • Ilo

    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!

    • Darren

      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.

      • Ilo

        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.

    • Alex

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

      • Ilo

        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

  • Darren

    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.

  • Rob G.

    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.

    • Alex

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

  • Rob G.

    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.

    • Rob G.

      Addendum: works fine with http://cpp.sh/
      Is it my console?
      Should I also reference the pointer being passed (n_ptr) as well?

    • Alex

      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.

      • Rob G.

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

        • Alex

          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.

          • Rob G.

            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!

  • Mauricio Mirabetti

    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

Leave a Comment

Put C++ code inside [code][/code] tags to use the syntax highlighter