Binary search is a method for quickly finding a specific target value in a sorted array. It begins by comparing the target value to the middle element of the array. Because the array is sorted, the comparison allows us to determine one-half of the array in which the target cannot lie. The search continues on the remaining half. By doing this repeatedly, we will eventually be left with a search space consisting of a single element, which would be the target value.

Example

In the example above, we're searching for the target value 4 in the given sorted array.

1. In the first step, we compare the middle element of the array 7 with the target value 4. Since 4 < 7, we can safely eliminate the right half of the array, including 7.
2. Now, we're left with elements 1-4 of the array. Since there are an even number of elements, we could pick element 2 or element 3 as the middle element. Let's say we pick element 2, which has a value of 3. Since 4 > 3, we can safely eliminate the left half of the current array, including 3.
3. We're left with elements 3-4. We could pick element 3 or element 4 as the middle element. Let's say we pick element 4, which has a value of 6. Since 4 < 6, we can safely eliminate everything to the right of 6, including 6.
4. We're only left with element 3. We verify that the value at element 3 is indeed the target value 4.