Binary search compares with the middle element, and then continues in one half only (the larger half has at most $\lfloor n/2 \rfloor$ elements). So in the worst case it makes one comparison and then searches an array of size $\lfloor n/2 \rfloor$, which gives $F(n) = F(\lfloor n/2 \rfloor) + 1$. This is the recurrence for $\lfloor \log_2 n \rfloor + 1$ comparisons.
More Searching and sorting algorithms questions
GATE 2024 DA Q45– Consider the following sorting algorithms: (i) Bubble sort (ii) Insertion sort (iii)…
GATE 2026 DA Q31– Let A be a sorted array containing 1000 distinct integers. You perform a recursive binary…
GATE 2026 DA Q49– Consider the problem of sorting the given array in ascending order: P = [1, 2, 3, 5, 4]…
GATE 2025 DA Q27– For which of the following inputs does binary search take time O( n) in the worst case?
GATE 2025 DA Q29– Suppose that insertion sort is applied to the array [1, 3, 5, 7, 9, 11, x, 15, 13] and it…