Number of comparison in best, avg and worst case in Binary Search

Question

So I basically want to know what will be the Best, Avg and Worst case no of comparisons taken by Binary Search on a Sorted Array of N elements. Consider Both cases where the element is present and not present in the Array

I have went online but unable to get a reliable and satisfactory answer

Answer 1

I think the worst case likely occurs when the target element is absent from the array. Hope this answer will help you out.

• Best Case: The best case occurs when the target value is located at the middle of the array. In this case, binary search makes exactly 1 comparison.
• Average Case: On average, binary search makes approximately log2(n) comparisons, where n is the size of the array. This is because with each comparison, binary search cuts the array in half. However, this is an approximation and the exact number can vary slightly.
• Worst Case: The worst case for binary search occurs when the target value is not in the array or when the target value is at one of the ends of the array. In this case, binary search makes exactly log2(n) + 1 comparisons. This is because it takes log2(n) comparisons to narrow down the search to a single element, and then one additional comparison to confirm that the element is not there (or is the target value).

Please note that log2(n) is rounded down to the nearest integer before adding 1. For example, if n = 10, log2(n) is approximately 3.32, which rounds down to 3. Adding 1 gives 4 comparisons in the worst case.