In the *Divide and Conquer* section of uHunt Chapter 3, one of the subsections is called *Binary Search the Answer*. Here’s how that technique works.

For a binary search problem like UVa 12192, the data to search is the input data. For that problem, you are given a rectangular grid of integers, and your goal is to find a square region that satisfies a particular property. One step in the process of finding that region efficiently is to run binary search on the data in a row.

Binary search problems like UVa 11413 and UVa 12032 require a different approach. Instead of binary searching the input data, you must search potential output values. The result of the search is the answer.

Competitive programming problem statements often specify the range of inputs that you are required to handle in your solution. For example, the description for UVa 12192 specifies that the grid cannot be larger than 500×500.

The input range is there for a few reasons. It lets you estimate the runtime of your solution before you submit, to avoid a Time Limit error. It also lets you choose an appropriate algorithm. If you determine that an $O(n^2)$ algorithm will run fast enough given the input size, then there’s no need to use an $O(n \log n)$ algorithm, which may take more time to implement. Finally, for search problems, the range tells you which values you have to search.

For *binary search the input* problems, you can directly plug the input range from the problem statement into the low and high values in your binary search function. For *binary search the output* problems, you may have to process the input first. Let’s look at a couple of examples.