A Level Computer Science OCR Practice Exam

What type of search algorithm relies on comparing the midpoint of an array?

1. Linear search

2. Depth-first search

3. Binary search

4. Index search

The correct answer is: Binary search

The binary search algorithm is designed specifically to operate on sorted arrays by effectively narrowing down the potential location of a target value. It works by first identifying the midpoint of the array. The algorithm then compares the target value to the value at this midpoint. If the target value is equal to the midpoint value, the search is complete. If the target is less than the midpoint, the algorithm restricts its search to the lower half of the array, and if it is greater, it searches the upper half. This halving process continues until the target value is found or the search range is exhausted. This efficient search method significantly reduces the number of comparisons needed compared to a linear search, which checks each element sequentially through the entire array. Binary search operates in \(O(\log n)\) time complexity, making it much more efficient for large datasets than methods like linear searching or index searching which do not assume the array is sorted.