ACM International Collegiate Programming
Divide and Conquer
This session focuses on binary search and divide and conquer. If you are not
familiar with the relevant concepts and algorithms, or you need a refresher,
you can use the resources below.
Problem Set (#3)
The Playboy Chimp
Note: All problems expect I/O to be done using standard input and standard
output. The solution to problems must be written in a single file.
If you are programming in Java the application class should be called
"Main" and should be in the default package.
Binary search is an efficient way of searching through an ordered set of objects to find
one that you are interested in (or find that it doesn't exist). The classic example is
searching through an ordered array, but there are many other ways to apply binary search:
finding a value in the range of a nondecreasing function, for instance, or searching for the
smallest "good" number in a range, where you know that if a number is "good", then so
are all larger numbers.
The basic algorithm is this: you have a search space you are looking through.
You take the midpoint of your search space, test it, and use that information to narrow
your search space down to half the size; either on one side of the midpoint or the other. Check out the wikipedia page for more information here.
Divide and Conquer
Divide and Conquer is a name for a class of recursive methods for solving problems.
Each recursive step looks something like the following:
- Take your problem of size N and divide it into a number of subproblems
of smaller size.
- Solve each of the subproblems recursively.
- Combine the solutions of the subproblems into a solution to the original
Often, we break the problem into two subproblems of half the size each, and
steps 1 and 3 take O(N) time.
In this case, Divide and Conquer results in a running time of O(N log N).
This isn't always
the case; in general, you can use the master theorem or just analyze the recursion tree
to find the running time of a Divide and Conquer algorithm. As recursive
algorithms in general are diverse, there are many variants on Divide and Conquer. Keep
an open mind while working!
Ternary search is an extension of binary search and occasionally comes up in ICPC.
If you are given a function that is not increasing or decreasing, but instead convex or
concave, it is possible to find the maximum or minimum of the function via ternary search,
in logarithmic complexity. The idea is instead of picking a single midpoint, we instead pick
two. Based on the values of the function at these midpoints, either the leftmost or rightmost
tri-section can be pruned. The details of ternary search can be found here.