Question

In binary search, after every pass of the algorithm, the search area:

• A. gets doubled
• B. gets reduced by half
• C. remains same
• D. gets reduced by one third

Hint:

Each iteration of binary search halves the problem size, making it logarithmic in time complexity.

Answer 1

The Correct Option is B

Step 1: Recall binary search mechanism.
Binary search iteratively divides the array into two halves using a mid index.
Step 2: Progress of search.
In each iteration, either the left or right half is eliminated, thereby reducing the search space by 50%.
Step 3: Efficiency.
This logarithmic reduction in search space confers efficiency on binary search, resulting in a time complexity of \(\mathcal{O}(\log n)\).
Step 4: Eliminate wrong options.
- Option 1: Incorrect, the size never increases.
- Option 3: Incorrect, the search space consistently decreases with each step.
- Option 4: Incorrect, the reduction is by half, not by one-third.

Final Answer: \[\boxed{\text{Gets reduced by half}}\]