Binary search is a highly efficient algorithm for finding elements in sorted arrays. Unlike linear search which checks every element one by one, binary search works by repeatedly dividing the search space in half. The key requirement is that the array must be sorted. Let's see how this works compared to linear search.
The binary search algorithm uses three key variables: left pointer marking the start of search range, right pointer marking the end, and mid pointer at the middle position. The core logic involves calculating the middle index using the formula mid equals left plus right minus left divided by two. We compare the target with the middle element, then eliminate half the search space based on the comparison. Let's trace through finding the value 11 in this sorted array.
Now let's examine the C++ implementation of binary search. The function signature takes an array, its size, and the target value. We declare three key variables: left starting at zero, right at n minus one, and mid calculated to prevent integer overflow. The while loop continues as long as left is less than or equal to right. We compare the middle element with our target and adjust the search boundaries accordingly. The function returns the index if found, or negative one if not found. Both iterative and recursive implementations are commonly used, with the iterative version being more memory efficient.