Explain binary search and its time complexity.

Binary search finds a target value in a sorted array by repeatedly dividing the search interval in half. Compare target with middle element: if equal, found; if target is smaller, search left half; if larger, search right half. Time complexity is O(log n) since each comparison eliminates half the remaining elements. Space is O(1) iterative or O(log n) recursive. Requires sorted input.