LAB 12C- 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:

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

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:

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.

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 sorted values.
• 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.