7.2. Recursion Problems

Recursive algorithms offer elegant solutions to problems that would be quite awkward to code nonrecursively. Interviewers like these kinds of problems because the answers are often short without being too simple.

7.2.1. Binary Search


Implement a function to perform a binary search on a sorted array of integers to find the index of a given integer. Use this method declaration:

int binarySearch( int[] array, int lower, int upper, int target );

Comment on the efficiency of this search and compare it with other search methods.

In a binary search, you compare the central element in your sorted search space (an array, in this case) with the item you're looking for. There are three possibilities. If it's less than what you're searching for, you eliminate the first half of the search space. If it's more than the search value, you eliminate the second half of the search space. In the third case, the central element is equal to the search item and you stop the search. Otherwise, you repeat the process on the remaining portion of the search space. If it's not already familiar to you from computer science courses, this algorithm may remind you of the optimum strategy in the children's number-guessing game in which one child guesses numbers in a given range and a second responds "higher" or "lower" to each incorrect guess.

Because a binary search can be described in terms of binary searches on successively smaller portions of the search space, it lends itself ...

Get Programming Interviews Exposed: Secrets to Landing Your Next Job, Second Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.