Twenty questions Binary search. In the game of "twenty questions", your task is to guess the value of a secret number that is one of the n integers between 0 and n−1. For simplicity, we will assume that n is a power of 2 and that the questions are of the form "is the number greater than or equal to x?"
An effective strategy is to maintain an interval that contains the secret number, guess the number in the middle of the interval, and then use the answer to halve the interval size. Questions. java implements this strategy. It is an example of the general problem-solving method known as binary search.

Analysis of running time. Since the size of the interval decreases by a factor of 2 at each iteration (and the base case is reached when n = 1), the running time of binary search is lg n.
Linear–logarithm chasm. The alternative to using binary search is to guess 0, then 1, then 2, then 3, and so forth, until hitting the secret number. We refer to such an algorithm as a brute-force algorithm: it seems to get the job done, but without much regard to the cost (which might prevent it from actually getting the job done for large problems). In the worst case, the running time can be as much as n.
Binary representation. If you look back to Binary. java, you will recognize that binary search is nearly the same computation as converting a number to binary! Each guess determines one bit of the answer. For example, if the number is 77, the sequence of answers no yes yes no no yes no immediately yields 1001101, the binary representation of 77.
Bisection search
Inverting an increasing function f(x). Given a value y, our task is to find a value x such that f(x) = y. We start with an interval (lo, hi) known to contain x and use the following recursive strategy:
Compute mid = lo + (hi − lo) / 2
Base case: If (hi − lo) is less than δ, then return mid as an estimate of x
Recursive step: otherwise, test whether f(mid) > y. If so, look for x in (lo, mid); if not look for x in (mid, hi).
The inverseCDF() method in Gaussian. java implements this strategy for the Gaussian cumulative density function Φ. In this context, binary search is often called bisection search.

Binary search in a sorted array
Binary search in a sorted array. One of the most important uses of binary search is to find an item in a sorted array. To do so, look at the array element in the middle. If it contains the item you are seeking, you are done; otherwise, you eliminate either the subarray before or after the middle element from consideration and repeat. BinarySearch. java is an implementation of this algorithm.
Insertion sort. Insertion sort is a brute-force sorting algorithm that is based on a simple method that people often use to arrange hands of playing cards: Consider the cards one at a time and insert each into its proper place among those already considered (keeping them sorted). The following code mimics this process in a Java method that sorts strings in an array:
public static void sort(String[] a) {
int n = a. length;
for (int i = 1; i 0; j--) {
if (a[j-1].compareTo(a[j]) > 0)
exch(a, j, j-1);
else break;
}
}
}
At the beginning of each iteration of the outer for loop, the first i elements in the array are in sorted order; the inner for loop moves a[i] into its proper position in the array by exchanging it with each large value to its left, moving from right to left, until it reaches its proper position. Here is an example when i is 6:
Insertion sort iteration
This process es executed first with i equal to 1, then 2, then 3, and so forth, as illustrated in the following trace.
Insertion sort trace

Analysis of running time. The inner loop of the insertion sort code is within a double nested for loop, which suggests that the running time is quadratic, but we cannot immediately draw this conclusion because of the break.
Best case. When the input array is already in sorted order, the total number of compares in ~ n and the running time is linear.
Worst case. When the input is reverse sorted, the number of compares is ~ 1/2 n2 and the running time is quadratic.
Average case. When the input is randomly ordered, the expected number of compares is ~ 1/4 n2 and the running time is quadratic.
Sorting other types of data. We want to be able to sort all types of data, not just strings. For sorting objects in an array, we need only assume that we can compare two elements to see whether the first is bigger than, smaller than, or equal to the second. Java provides the Comparable interface for this purpose. Insertion. java implements insertion sort so that it sorts arrays of Comparable objects.