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.
In binary search, the array is divided into two halves at each iteration using mid index.
Step 2: Progress of search.
At each pass, either the left half or the right half is discarded, reducing the search space by 50%.
Step 3: Efficiency.
This logarithmic halving of search space makes binary search efficient with time complexity \(\mathcal{O}(\log n)\).
Step 4: Eliminate wrong options.
- Option 1: Wrong, size never increases.
- Option 3: Wrong, search space reduces each step.
- Option 4: Wrong, reduction is by half not one third.

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