Binary search is one of the most fundamental and efficient algorithms in computer science. It allows us to find a target value in a sorted array by repeatedly dividing the search space in half. The key requirement is that the data must be sorted beforehand. Here we have a sorted array with ten elements.
Let's see how binary search works step by step. We want to find the target value thirteen in our sorted array. First, we set left pointer at index zero and right pointer at index nine. Then we calculate the middle index, which is four. The middle element is nine, which is less than our target thirteen, so we search the right half.
Let's trace through the first iteration of our binary search example. We start with left pointer at index zero and right pointer at index nine. The middle index is calculated as zero plus nine divided by two, which equals four. The element at index four is nine. Since nine is less than our target thirteen, we eliminate the left half and move our left pointer to index five.
Now for iteration two. Our left pointer is at index five and right pointer at index nine. The new middle is seven. The element at index seven is fifteen, which is greater than our target thirteen. So we eliminate the right half and move our right pointer to index six. Now left equals right at index six, and we check: array at index six equals thirteen. We found our target!
To summarize what we've learned about binary search: it requires sorted data as a prerequisite. The algorithm works by dividing the search space in half with each iteration, giving it an efficient time complexity of O log n. This makes it much faster than linear search for large datasets, which is why it's widely used in databases and search algorithms throughout computer science.