Free Response Question: Recursive Binary Search

Background

In Unit 7, we covered a searching algorithm known as binary search. We used an iterative approach to search for an element in an array.

In this challenge, you’re required to recursively implement the binary search algorithm.

Problem statement

Intent: Design a recursive search method to implement the recursive binary search algorithm.

• Create two methods:

  • The binarySearch() method
  • The search() method

  The binarySearch() is a non-recursive method that only takes an array and a value to be searched for as input. It returns the position of the value in the array. The search() is a recursive method that takes the array, the value, left, and right. It returns the position of the value in the array.

  The difference is that we’ll call binarySearch() from main and search() will be called by binarySearch(). From there, only search() is responsible for handling recursion (base case and recursive case).

• Think about base cases.