The GATE Grind

GATE 2025 CS (CS2) – Question 41

Algorithms · Searching, Sorting and Hashing · 2 marks · Multiple choice

An array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1 \le i \le n$ such that $A[1..i]$ is sorted in the non-decreasing order and $A[i+1..n]$ is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array $A$?

  1. $\Theta(n)$
  2. $\Theta(1)$
  3. $\Theta(\log^2 n)$
  4. $\Theta(\log n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $\Theta(\log n)$

Explanation

**Finding the peak.** Because the array first increases and then decreases, compare `A[mid]` with `A[mid+1]`:
- if `A[mid] < A[mid+1]`, the peak is to the right,
- otherwise the peak is at `mid` or to the left.

Each comparison halves the range, so the peak is found with $O(\log n)$ comparisons.

**Searching.** The part to the left of the peak is sorted increasing and the part to the right is sorted decreasing. Run a binary search on each: $O(\log n)$ each.

Total: $\Theta(\log n)$. A lower bound of $\Omega(\log n)$ holds for searching in any sorted-like structure, so the answer is $\Theta(\log n)$: option (D).

More Searching, Sorting and Hashing questions

All Searching, Sorting and Hashing questions →