Question

In a binary search, after three comparisons have been made, only ________ of the array will be left to search.

Short answer

Answer: After three comparisons in a binary search, only 1/8 of the array will be left to search.

Step-by-step solution

Recall Binary Search Operation

In a binary search, the array must be sorted before starting the search process. During the search, the middle element is compared to the desired value. If the desired value equals the middle element, the search is successful. If it is less than the middle element, the search continues on the lower half of the array. If it is greater than the middle element, the search continues on the upper half of the array. After each comparison, the search space is reduced by half since the algorithm eliminates the part of the array that does not contain the desired value.

Perform First Comparison

After the first comparison is made, the search space is reduced by half. To know the remaining part of the array to search, we can represent this as a fraction: remaining part after 1st comparison is \(\frac{1}{2}\).

Perform Second Comparison

After the second comparison is made, the search space is reduced by half again. To know the remaining part of the array to search, we multiply the remaining part after the 1st comparison by \(\frac{1}{2}\): remaining part after 2nd comparison is \(\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}\).

Perform Third Comparison

After the third comparison is made, the search space is reduced by half once more. To know the remaining part of the array to search, we multiply the remaining part after the 2nd comparison by \(\frac{1}{2}\): remaining part after 3rd comparison is \(\frac{1}{4} \times \frac{1}{2} = \frac{1}{8}\).

Conclusion

After three comparisons have been made in a binary search, only \(\frac{1}{8}\) of the array will be left to search.