Binary Search

Binary search finds a value in a sorted array by comparing it with the middle item and discarding the half that cannot hold it, so it needs about log2 n comparisons where a scan from the front needs up to n. It matters because nearly every fast lookup in sorted data is a binary search, and because later algorithms, from costing divide and conquer to searching a range of possible answers, reuse the same halving. The topic traces a search that finds its target and one that misses, then states the loop invariant that makes the search correct and explains why the bounds move past the middle. It shows the Java midpoint that overflows, extends the search to lower and upper bounds for repeated values, implements both versions in three languages beside Python's bisect and Java's Arrays.binarySearch, decodes the negative number Java returns on a miss, and ends with an exercise on a shop's sorted price list.