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

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

127 comments to 7.x — Chapter 7 comprehensive quiz

  • Sid

    How does this prevent an overflow?

    And why might

    cause an overflow?

    It might be better if you could give an example.

    Thanks!

  • Ngô Hoàng Đạt

    Hi Alex and Nascardriver
    I have a question that is "when we should use iteration version and when we should use recursion version."

  • Silviu

    I understand this, but not sure if i'm thinking correct- in my binarySearch i have "target" and it's replaced with testValues[count].(which i'm guessing it's taking the number under the testValues[0]=0, because we have a loop and loop through all of them).

    So basically the output will be all the numbers of the testValues[] { 0, 3, 12, 13, 22, 26, 43, 44, 49 }, because the     expectedValues[] = { -1, 0, 3, -1, -1, 8, -1, 13, -1 } are equal with the return of the numbers of the binarySearch function
    that are tested with this(to output them):

    Correct ?

    • Alex

      Yep, we're testing the algorithm with each value in testValues and making sure the answer matches what's in our expectedValues array. If so, then we can be pretty confident it works as desired.

      • Silviu

        Thank you ! In binarySearch we always know the target, no ? like in your example with one single array , or like in the quiz where relatively know the targets. Binary Search is more of a efficient way to a better search algorithm and memory use no ?

  • Kunal

    Hello there!
    I'm having an issue with my code in the sense that i can't understand why changing a certain piece of code made it work,(This is the solution to 3b) the code
    is:

    My issue is the else if at line 15, when I used only an if, the program gave me fails for all numbers after 12, but adding the else meant a pass on all test values,
    I don't see how changing the if to else if could have affected my program so drastically, and that's what i want to understand. All help appreciated!

  • Matt

    Hello, my answer to 3b (the recursive solution to binary search) was very similar to the solution posted by Alex.

    The only difference was that Alex's solution returned the recursive call to the binarySearch function, whereas mine just called it.

    The relevant snipped from Alex's solution:

    And mine:

    Is there any difference between returning the recursive function call and simply calling it there and then? Or are they identical in the end result?

    • Hi Matt!

      Your function doesn't return, the return value is undefined, your compiler should've told you, read the warnings.
      The reason why your program works is that @binarySearch is the last function you call in @binarySearch, so the outer call will return the value that the recursive call returned (Because of how function calls work on a low level). You might not get that lucky on other architectures.

  • Vamshi malreddy

    For Q3.
    what does this do..
    int binarySearch(int *&array, int target, int min, int max)
    {
    ...
    }

    what exactly am I passing as an argument in case of array?

    thank you

  • alioow

    Hi , the solution of question 3a) is wrong , its because when u return -1 and it checks with expectedValues[count] , in the "expectedValues" array u added -1 for wrong numbers,
    u must always return midpoint for correction .
    thanks

  • Peter Baum

    Comments on the provided 3a solution:

    1. The solution given for 3a does not check to see if the argument for the array is nullptr.  The program will crash with such an argument unless a check is made.

    2. The solution given for 3a does not include const in parameter specifications.  That might represent an improvement.

    • Alex

      1) Added assert to 3a and 3b to check for existence of array.
      2) Pass by value parameters are most often not consted even if they could be because the value from doing so is typically so low. You can certainly const yours if you like, but it's such a widespread practice not to that I don't consider it incorrect not to.

  • Peter Baum

    3. When the midpoint is calculated and used as a new bound, we can choose the properties we want for that bound.  In the given solution, it is assumed that the bound we want might be the index for the value we are searching.  (This is analogous to closed intervals in mathematics.)  The choice made in the given solution is obvious when one is either added or subtracted from the midpoint of the range being examined.  That isn’t always the most efficient way to search, because it doesn’t take advantage of the fact that if the bounds exclude the target index (analogous to an open interval in mathematics), we can stop checking earlier in the process.
    Let’s call the bounds normalized if they act like open intervals, i.e., that they exclude the possibility that they can be an index for the target array element.  Every time we move min or max, they have this property.  Note, however, that we might not move one or the other during a search, which means that one of these unmoved bounds may be un-normalized.   Therefore, to address this issue, you have to either keep track of whether the bounds have been moved or normalize the bounds initially.  If they are initially normalized (either by convention or at runtime by the code) we do not have to worry about them afterwards.  

    The timesaving isn’t a black and white issue though, because we gain a little bit by decreasing the range if we use closed, un-normalized bounds.  In terms of time, the un-normalized approach also has to add and subtract 1 through each iteration.  The normalized version has an extra add one as part of the while loop condition.  To determine the benefits of an approach, we can put in a counter to see how many times we have to go through our search loop or put in timing code to test for overall efficiency.  For now, I just put in a counter and discovered that I could get about a 39% decrease in iterations using the normalized approach.  Maybe that is a little biased though because the normalization process eliminates any loops that occur at the locations where a binary search has to work the hardest.  Still, the results are encouraging.

    Note that, in spite of the comments in the given solution to 3a, with normalization, we do not test any elements of the array more than once.

    Here is a binary search routine that implements this normalization approach:

    • Peter Baum

      I updated the routine to make it faster.  One egregious mistake was the test order within the while loop.  Here is my latest version:

  • Peter Baum

    Quiz 2e

    Also there seems to be a problem within the for loop.  Probably the intent is to output the arguments rather than the numbers used to index the arguments.

    • Alex

      Addressed all of the issues in your prior comments. Thanks!

      Pass by value parameters are typically not made const because the value from doing so is almost zero.

  • Peter Baum

    quiz 2c
    Add - there is also a potential divide by 0 issue.

  • Peter Baum

    Regarding quiz 1a: Although not necessary, would it be better to write:

    ?

  • Peter Baum

    5th paragraph: "The return value is not considered a parameter."

    When was the return value of a function ever considered a parameter?

  • Peter Baum

    4th paragraph: "You should not need to use this."

    I would add "because the compiler will usually make such choices for you."

  • Peter Baum

    In the second paragraph it says "Use pass by (const) reference for structs, classes, or when you need the function to modify an argument."

    That will be confusing, because the following won't compile because of const:

  • Donlod

    A question related to 1c, this is the code so far:

    I then tried to declare @a as a pointer to an int instead just to get a bit more confident with pointers and refs.
    So as far i understand when declaring @a as ptr i need to assign the address of the returned value because the returned value comes with an implicit dereference right?

    This somehow confused me a bit with the previous assignment using the reference

    How does @a know that the right hand side is a reference to an int, since on the right hand side the result is implicitly dereferenced. Does @a recognize that because @a itself is declared as a reference and therefore storing the address of the right hand side instead of the dereferenced value?

  • Cumhur

    Hi!
    This is my solution open for your suggestions.

    • nascardriver

      Hi Cumhur!

      * Initialize your variables with uniform initialization.
      * Mathematically ((min + max) / 2) = (min + (max - min) / 2), but the left side of the equation is more prone to an overflow, because (min + max) might result in quite a large number.
      * Line 5: Should return @average
      * Line 6: You already know array[average] != target. There's no point in checking it again.
      * @binarysearch is causing a warning "control reaches end of non-void function". This isn't actually true, but it's an indicator for bad code. Replace the second inner if-statement with an else-if-statement and return -2 at the end of the outer if-statement.
      * Your while loop should've been inside @binarysearch.

  • J Gahr

    Here is my solution to 3a. Any comments for improvement?

    Edit: Here is my solution to 3b. It took less time than I thought it would.

    • nascardriver

      Hi J!

      Good job on solving the quiz!

      Suggestions:
      * Use uniform initialization.
      * Mathematically ((min + max) / 2) = (min + (max - min) / 2), but the left side of the equation is more prone to an overflow, because (min + max) might result in quite a large number.
      * In your iterative function you have a repetition of (center = (max + min) / 2), this should be avoided.
      * I would've split line 10 in your recursive function into separate lines for readability.

      • J Gahr

        Thanks for the suggestions, I've updated 3b accordingly.

        • nascardriver

          I was thinking about temporaries, because your approach could be undone by different formatting options of the editor.

  • Matt

    Alex,

    I'm curious how overflow as result of integer addition would be of concern in this example considering that the "stack" would probably overflow from creating an array large enough to provide overflow-capable values of min and max in the first place.

    Assuming a 32 bit integer, it could hold values up to +/- 2147483647 (if I'm not mistaken).

    Given the following:

    (min + max) would have to be larger than 2147483647...I just don't see how we could be dealing with an array large enough to have indices that large anyways (and certainly not in the example code).

    Regardless, your method of calculating the input makes sense, as the value of the integer (during calculation) never exceeds its original value...but am I misinterpreting your intention?

    • Alex

      A couple of thoughts here:
      1) int could be 2 bytes on some machines, in which case (min + max) would only have to be greater than 32,767, which is much more doable.
      2) The array passed in could have been dynamically allocated, which doesn't use the stack.

      It's always better to program defensively, even if you don't think something is possible.

  • Kushagra

    In 3b , can this code can be used?
    #include <iostream>
    bool odd( int x , int y )
    {
    double f = (x+y)/2;
    int i = (x+y)/2;
    if (f!=i)
    return true;
    else
    return false;

    }
    int binarySearch( int * array , int test , int min, int max)
    {
    int centre;

    if ( odd(min , max))
    {
    centre =( (min + max)/2) ;
    }
    else
    centre = (min + max)/2 ;

    if (test > array[centre])
    min = centre +1;
    if ( test < array[centre])
    max = centre -1;
    if (test == array[centre])
    return centre;
    if (min > max)
    return -1;
    return  binarySearch(array ,  test , min , max);

    }
    int main()
    {
    int array[] = { 2 ,4 ,6 ,8 ,21, 23 , 56 ,73 ,74 , 86 ,99 ,100};
    int numtest = 6;
    int test[] = { 0 , 3 ,5 ,54 ,56 ,73 };
    int expected[] = { -1,-1,-1, -1 , 6 , 7};
    for (int count = 0; count < numtest ; count++)
    {
    int index = binarySearch(array , test[count] , 0 , 11);

    if ( index >=0)
    std::cout << test[count] << " is found \n";
    else
    std::cout << test[count] << " is not found \n";
    }
    return 0;
    }

    • Alex

      I think so. But a couple of minor things:

      1) Your function to determine if an integer is odd is way more complicated than necessary. You can use this:

      2) Your midpoint calculation is subject to overflow if one or both of the numbers is large.

Leave a Comment

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