Show the number of elements comparison with example and proof of Binary search for Average, best and worst time case analysis.
Number of Element Comparisons in Binary Search:
In each step of Binary Search, we reduce the search space by half. We can calculate the number of element comparisons by considering how many times we can halve the array until we find the element or determine it’s not present.
The maximum number of comparisons needed is equal to the number of times we can halve the array until we reach a single element (or determine it’s not present).
For a list or array of size n, the maximum number of comparisons needed is log₂(n). This is because we halve the array in each step, and it takes log₂(n) steps to reduce n to 1.
Time Complexity Analysis:
- Best Case:
- The best-case scenario occurs when the target element is exactly in the middle of the array.
- In this case, we find the element in the first comparison.
- Therefore, the best-case time complexity is O(1).
- Average Case:
- In the average case, we consider the element could be anywhere in the array.
- We reduce the search space by half in each step, so the average number of comparisons is log₂(n).
- Therefore, the average-case time complexity is O(log₂(n)).
- Worst Case:
- The worst-case scenario occurs when the target element is not present in the array, and we’ve narrowed the search to a single element.
- We reduce the search space by half in each step, so the maximum number of comparisons needed is log₂(n).
- Therefore, the worst-case time complexity is O(log₂(n)).
Example:
Let’s consider an example where we want to find the element 8 in a sorted array of size 8: [1, 3, 4, 5, 6, 8, 9, 10]. We’ll illustrate the number of comparisons needed in each case:
- Best Case: Element 8 is in the middle (1 comparison).
- Average Case: log₂(8) = 3 comparisons (at most).
- Worst Case: Element 8 is not present (log₂(8) = 3 comparisons at most).