Problem Statement
The binary search method needs no more than ________ comparisons for an array of size n.
Explanation
Binary search requires at most log base 2 of n plus 1 comparisons. The algorithm divides the search space in half with each comparison, leading to logarithmic time complexity.
For example, with an array of 16 elements, binary search needs at most log base 2 of 16 plus 1 equals 5 comparisons. The plus 1 accounts for the final comparison that determines the exact match or confirms the element is not present. This is significantly better than linear search which requires n comparisons in the worst case.
Code Solution
SolutionRead Only
// Binary Search - O(log n) comparisons
int binarySearch(int arr[], int target, int left, int right) {
if (right >= left) {
int mid = left + (right - left) / 2;
// Element found at mid
if (arr[mid] == target)
return mid;
// Search left half
if (arr[mid] > target)
return binarySearch(arr, target, left, mid - 1);
// Search right half
return binarySearch(arr, target, mid + 1, right);
}
return -1; // Element not found
}
// For n=16: max comparisons = log2(16) + 1 = 4 + 1 = 5