Introduction to Divide-and-Conquer Algorithms

Divide-and-conquer algorithms

In this chapter, we’ll learn about divide-and-conquer algorithms, which will help us search huge databases a million times faster than brute force algorithms. Armed with this algorithmic technique, we’ll learn that the standard way to multiply numbers (which we learned in grade school) is far from being the fastest!

We will then apply the divide-and-conquer technique to design fast-sorting algorithms. We will learn that these algorithms are optimal; that is, even the legendary computer scientist Alan Turing would not be able to design a faster sorting algorithm!

We will be looking at the following divide-and-conquer programming challenges:

---

Sorted array multiple search

Search multiple keys in a sorted sequence of keys.

Input: A sorted array $K$ $=$ [$k_{0}$,$\ldots$, $k_{n-1}$] of $n$ distinct integers and ...