申論題

Binary search is an efficient algorithm for finding an item from a sorted array of items. It works by repeatedly dividing in half the part of the array that could contain the item until you've narrowed down the possible locations to just one.

To find the maximum number of comparisons in a binary search, we use the formula for the height ℎh of a perfect binary tree, which is ℎ=⌈log⁡2(n+1)⌉, where n is the number of elements in the array, and ⌈x⌉ denotes the ceiling function, which rounds x up to the nearest integer.

For an array of 2000 elements, the maximum number of comparisons would be one more than the height of the tree because you compare once at each level of the tree. Let's calculate this value.

The maximum number of comparisons that a binary search algorithm could possibly make when searching for a value in a 2000-element array is 11.