Intermediate C Programming, 2nd Edition

Chapter 16Programming Problems Using Recursion

DOI: 10.1201/9781003257981-16

This chapter describes several problems that can be solved using recursion.

16.1 Binary Search

A binary search is an efficient way to search for a value in a sorted array. The function search returns the index of the key within arr. If arr does not contain this key, then the function returns $-1$. The arguments mean the following:

• arr: an array of integers. The elements are distinct and sorted in the ascending order.

• len: the length of the array, i.e., the number of elements in the array.

• key: the value to search for. Think of key as the proverbial needle in the haystack.

Since the array is already sorted, it is possible to quickly discard many elements (nearly half) ...