LAB 12B- BINARY SEARCH
Concepts
Focus on just one concept for this assignment: using a recursive strategy to search an array that has been sorted.
Recursion (Functions that Call Themselves)
You may have noticed in our previous discussions how a function can call another function (e.g., a class member function calls a helper function to get something done). What happens when we have a function that calls itself? Consider this implementation of pow
:
return (base * Pow(base, (exponent - 1)) );
}
Yikes, what is going on here? This function returns the base it receives times the result of Pow(base, exponent - 1)
, then returns that value to the caller. But there's a problem. Let's take a look at calling Pow(2, 3)
.
Call | Return value |
Pow(2, 3) | 2 * Pow(2, 2) |
Pow(2, 2) | 2 * Pow(2, 1) |
Pow(2, 1) | 2 * Pow(2, 0) |
Pow(2, 0) | 2 * Pow(2, -1) |
Pow(2, -1) | 2 * Pow(2, -2) |
Uh oh!
The problem in the above code is that the function will run "forever." Why? Because there is no "stopping condition." When you are implementing a recursive function, you should first decide "what is the stopping condition" or "what is the most simple case of this function that can return a value, rather than call itself?"
Let's fix the above implementation. What is the "most simple case" in the above implementation? When exponent
is 1
, we can just return base
since any base raised to the power of 1
is the value of the base (21
is 2
). Let's take a look:
if (exponent == 1) {
return base;
}
else {
return (base * Pow(base, (exponent - 1)) );
}
}
That's better. This function will recurse until it gets to "the bottom" where exponent
is 1
. When Pow(2, 1)
gets called, it merely returns 2
, rather than making another call to itself.
Call | Return value |
Pow(2, 3) | 2 * Pow(2, 2) |
Pow(2, 2) | 2 * Pow(2, 1) |
Pow(2, 1) | 2 |
The point we are emphasizing here is that you should first think of stopping conditions in recursive function definitions. Otherwise, you'll likely end up with an unintended result or a recursive function that does not stop. Can you say, "Stack Overflow?"
Instructions
There are many real-world problems that one would likely implement with a recursive algorithm (e.g., factorial, GCD, etc.). In this lab, implement the Binary Search algorithm (discussed in class) as a recursive function.
Requirements:
- Read the values in this file into a 1D array of integers. NOTE: The file has exactly 1,000 values.
- Sort the elements in the array in ascending order. Your solution to Lab 09A should be useful.
- Ask the user what value they would like to search within the array.
- Call your recursive function to do the searching. The function should
return a
bool
on whether the value was found. - Output whether the value was found.
Your solution to this lab will be due with Homework 12. While the due date of Homework 12 is after Exam II, we encourage you to do this lab now (as recursion is a topic on the exam).