Binary search finds a target value inside a sorted array by repeatedly cutting the search range in half. It compares the target to the middle element: if they match, the search is done; if the target is smaller, the search continues in the lower half; if larger, in the upper half. Each comparison discards half of the remaining candidates, so the number of comparisons grows only as the logarithm of the array size, giving O(log n) running time. The catch is that the data must already be sorted, which is what lets the algorithm decide which half to throw away.
The method is a textbook example of divide-and-conquer: a problem is solved by reducing it to a smaller version of itself. The cost of building the precondition is that the array must be kept in order, which is why binary search pairs naturally with sorting and with ordered structures such as the binary search tree.
Donald Knuth treats searching by comparison of keys, including binary search and the search of an ordered table, in Volume 3 of The Art of Computer Programming, whose Chapter 6 is devoted to searching. He is also the source of the often-repeated observation that although the idea is simple, getting every boundary case right is surprisingly hard: a correct, fully general version of binary search was not published until many years after the idea first appeared.
Despite looking trivial, binary search is famous for off-by-one bugs. The midpoint calculation, the choice of whether a bound is inclusive or exclusive, and the loop’s stopping condition all have to agree, or the search can skip the target or loop forever. The MIT 6.006 lecture notes on sorting frame the broader point: in the comparison model, any search that only compares keys needs on the order of log n comparisons in the worst case, which is exactly what binary search achieves.