GATE CSE 2025 | Set 2 | Question: 31

Question

​​An array $A$ of length $n$ with distinct elements is said to be bitonic if there is an index $1 \leq i \leq n$ such that $A[1 . . i]$ is sorted in the non-decreasing order and $A[i+1 \ldots 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$ ?

• A. $\Theta(n)$
• B. $\Theta(1)$
• C. $\Theta\left(\log ^{2} n\right)$
• D. $\Theta(\log n)$

Comments

https://www.geeksforgeeks.org/dsa/find-element-bitonic-array/

---

I will come here if bitonic repeats

 

---

@Anmol_Sharma2003what do you mean by the term inversion

Answer 1

Answer : D

To apply the binary search we need sorted array ,we can divide given array as 2 sorted arrays if we know peak element ,so we first find peak element :

• Elements right to the peak element are in decreasing order

• ---

  Elements left to the peak element are in increasing order

To search in a bitonic array:

1. Find the peak (maximum) element.

   • Use modified binary search.

   • Takes Θ(log⁡n) time.

2. Once the peak is found:

   • Apply binary search on the increasing part.

   • Apply binary search on the decreasing part.

   • Each takes Θ(log⁡n)  time.

So total time is:

Θ(logn)+Θ(logn)+Θ(logn)=Θ(logn)

 

---

To find Peak Element Algorithm:

def find_peak(A):
    low = 0
    high = len(A) - 1

    while low <= high:
        mid = (low + high) / 2

        # Handle boundaries
        if mid > 0 and mid < len(A) - 1:
            if A[mid] > A[mid - 1] and A[mid] > A[mid + 1]:
                return mid  # Peak found
            elif A[mid] < A[mid + 1]:
                low = mid + 1  # Move right
            else:
                high = mid - 1  # Move left
        elif mid == 0:
            if A[0] > A[1]:
                return 0
            else:
                return 1
        elif mid == len(A) - 1:
            if A[-1] > A[-2]:
                return len(A) - 1
            else:
                return len(A) - 2

---

Example: Array [2, 4, 5, 7, 6, 3]

Step-by-step:

1. low = 0, high = 5 → mid = 2 → A[2] = 5, A[3] = 7 → 5 < 7 → move right

2. low = 3, high = 5 → mid = 4 → A[4] = 6, A[5] = 3 → 6 > 3 and 6 < 7 → move left

3. low = 3, high = 3 → mid = 3 → A[3] = 7, A[2] = 5, A[4] = 6 → 7 > 5 and 7 > 6 → peak found

 

 

Comments

if this is best possible asymptotic bound then what will be worst possible asmptotic bound?

---

hmm the worst possible asymptotic bound might use linear search.......

---

"best possible bound" here means the bound of the best possible algorithm. So "worst possible bound" is ill defined since a terrible algorithm might be such that it runs indefinitely.

Answer 2

Just apply binary search algorithm from index 1 to i  so log n and again binary search from index i+1 to n so log n then do one thing and logn to find the peak so overall 3 logn so final answer is logn.

Comments

@Kishori_Arora the Array is of distinct elements so no equal sign.

---

distinct elements.

 

---

Best Answer.

Answer 3

We are given a bitonic array $A[1..n]$ of distinct integers: it strictly increases to a unique peak and then strictly decreases. The goal is to determine the worst-case number of comparisons required to search for a given key.

The optimal strategy consists of two phases:

1. Locate the peak element using a modified binary search.
2. Perform binary search in the increasing and/or decreasing segment.

Both phases run in $O(\log n)$ time, and a matching $\Omega(\log n)$ lower bound holds, yielding $\Theta(\log n)$.

We illustrate the process with the example array:
\[
A = [2,\ 5,\ 8,\ 12,\ 15,\ 13,\ 10,\ 6,\ 3], \quad n = 9.
\]

The array with indices is represented as:
\[
\begin{array}{c|ccccccccc}
i      & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
A[i]   & 2 & 5 & 8 &12 &15 &13 &10 & 6 & 3
\end{array}
\]

We search for the key $x = 10$.

 

$\textbf{Phase 1: Find the peak index}$

We maintain pointers $\texttt{low}$ and $\texttt{high}$, initially $\texttt{low}=1$, $\texttt{high}=9$. At each step, compute $\texttt{mid} = \lfloor(\texttt{low}+\texttt{high})/2\rfloor$, and compare $A[\texttt{mid}]$ with $A[\texttt{mid}+1]$.

$\textit{Iteration 1:}$
\[
\texttt{low}=1,\quad \texttt{high}=9,\quad \texttt{mid}=5
\]
\[
\begin{array}{c|ccccccccc}
i      & 1 & 2 & 3 & 4 & \color{blue}{5} & \color{red}{6} & 7 & 8 & 9 \\ \hline
A[i]   & 2 & 5 & 8 &12 & \color{blue}{15} & \color{red}{13} &10 & 6 & 3
\end{array}
\]
Since $A[5] = 15 > 13 = A[6]$, we are on the decreasing side. Set $\texttt{high} \gets \texttt{mid} = 5$.

$\textit{Iteration 2:}$
\[
\texttt{low}=1,\quad \texttt{high}=5,\quad \texttt{mid}=3
\]
\[
\begin{array}{c|ccccccccc}
i      & 1 & 2 & \color{blue}{3} & \color{red}{4} & 5 & 6 & 7 & 8 & 9 \\ \hline
A[i]   & 2 & 5 & \color{blue}{8} & \color{red}{12} &15 &13 &10 & 6 & 3
\end{array}
\]
Since $A[3] = 8 < 12 = A[4]$, we are on the increasing side. Set $\texttt{low} \gets \texttt{mid}+1 = 4$.

$\textit{Iteration 3:}$
\[
\texttt{low}=4,\quad \texttt{high}=5,\quad \texttt{mid}=4
\]
\[
\begin{array}{c|ccccccccc}
i      & 1 & 2 & 3 & \color{blue}{4} & \color{red}{5} & 6 & 7 & 8 & 9 \\ \hline
A[i]   & 2 & 5 & 8 & \color{blue}{12} & \color{red}{15} &13 &10 & 6 & 3
\end{array}
\]
Since $A[4] = 12 < 15 = A[5]$, set $\texttt{low} \gets 5$.

Now $\texttt{low} = \texttt{high} = 5$. The peak is at index $p = 5$.

This phase uses at most $\lceil \log_2 n \rceil$ comparisons.

 

$\textbf{Phase 2: Search in sorted subarrays}$

Split the array at the peak:

• Increasing part: $A[1..5] = [2,5,8,12,15]$
• Decreasing part: $A[6..9] = [13,10,6,3]$

First, perform standard binary search on $A[1..5]$ for $x=10$ → not found.

Next, search in the decreasing segment $A[6..9]$. Use a binary search adapted for decreasing order:

Initialize $\texttt{low}=6$, $\texttt{high}=9$.

$\textit{Search step:}$
\[
\texttt{mid} = \left\lfloor \frac{6+9}{2} \right\rfloor = 7
\]
\[
\begin{array}{c|ccccccccc}
i      & 1 & 2 & 3 & 4 & 5 & 6 & \color{green}{7} & 8 & 9 \\ \hline
A[i]   & 2 & 5 & 8 &12 &15 &13 & \color{green}{10} & 6 & 3
\end{array}
\]
$A[7] = 10 = x$ → key found.

In the worst case (e.g., key absent), this phase requires at most $\lceil \log_2 n \rceil$ comparisons per half, so at most $2\lceil \log_2 n \rceil$ total.

$\textbf{Total Complexity}$

• Peak finding: $\leq \lceil \log_2 n \rceil$ comparisons.
• Searching two halves: $\leq 2\lceil \log_2 n \rceil$ comparisons.

Thus, total comparisons $\leq 3\lceil \log_2 n \rceil = O(\log n)$.

Moreover, any comparison-based search among $n$ distinct elements requires $\Omega(\log n)$ comparisons (decision-tree lower bound). Since the increasing half alone contains $\geq n/2$ sorted elements, this bound applies.

Therefore, the worst-case number of comparisons is tightly bounded as:
\[
\boxed{\Theta(\log n)}
\]

Hence, the correct choice is D. $\Theta(\log n)$.

Answer 4

Answer - D

Best possible asymptotic bound is same as Best algorithm Worst case
Binary Search can only be applied on sorted array , So we have to find peak first and apply binary search on left and right . How to find peak ? Use binary search . But how do we use binary search in unsorted array use condition
 if (arr[mid] > arr[mid + 1])   
high = mid;
}
else {  low = mid + 1;
}

So  logn to find peak and 2 logn for left and right subarray - O(logn) asymptotically

Comments

I think your peak finding algorithm is not working properly for all the cases like for A = {1,3,2,2,2}.

---

@Ritik tiwari we have to take distinct elements as it is mentioned in the question itself "array of length n with distinct elements"

Answer 5

Here the array is considered Bitonic which can be represented as a Hill where the peak of the array is largest value. This is not sorted array so we cannot use Binary search directly but what we can use is Modified Binary Search which will find the peak element.
Answer : D  Finding peak O(logn), searching in any of the half will take O(logn) => O(logn)
int l=0, r=n-1;

int mid=(r+l)/2;

while(l<r){

if(arr[mid]<target) l=mid+1;

else r=mid;

}

if(arr[l]==target) return l;

return -1;

Comments

you algorithm does not work here:

eg: $0  \\\ 2 \\\ 4 \\\ 6 \\\ 8 \\\ 7 \\\ 5 \\\ 3 \\\ 1$

target = $1$

$l = 0, \\\ r = 8$

$mid = 4$

so $if$ fails then $r = mid \\\  \& \\\ l = 0$

now we dont have $1$ in left subarray

---

In the question it is told all the elements are distinct why you are taking duplicate elements? @RahulVerma3

---

totaly missed the detail, corrected

Answer 6

ANSWER :- OPTION D : O(log n)
Reason:
First, we find the peak element (bitonic point) using binary search in O(log n) time by comparing the middle element with its neighbors and moving either left or right accordingly.
After finding the peak, we perform binary search separately on the increasing part (left side) and the decreasing part (right side) — each taking O(log n) time.
Therefore, the total time complexity remains O(log n) (since constants don’t affect asymptotic behavior), and the worst-case bound is Θ(log n).

EXAMPLE :-  
A = [1, 3, 8, 12, 9, 5, 2]
Here,
The array first increases: 1 → 3 → 8 → 12
Then decreases: 12 → 9 → 5 → 2
So, 12 is the bitonic peak element.

Step 1: Find the Peak (Bitonic Point)
We can find the peak using binary search:
Set low = 0, high = n-1
Find mid = (low + high) / 2
Compare A[mid] with its neighbors:
If A[mid-1] < A[mid] > A[mid+1], then A[mid] is the peak.
If A[mid] < A[mid+1], then move right (peak lies ahead).
If A[mid] > A[mid+1], then move left (peak lies before).
For A = [1, 3, 8, 12, 9, 5, 2]:
mid = 3 → A[3] = 12
A[2] = 8 < 12 and A[4] = 9 < 12
So 12 is the peak (found in O(log n)).

Step 2: Search for the Target Element

Let’s say we want to search 9 in the array.
We now have two sorted parts:
Increasing part: [1, 3, 8, 12]
Decreasing part: [12, 9, 5, 2]

We perform binary search:
On the left (increasing order) → not found
On the right (decreasing order) → found 9
Each binary search takes O(log n) time.
Step 3: Combine the Steps

Finding the peak element → O(log n)

Binary search on the increasing part → O(log n)

Binary search on the decreasing part → O(log n)

So, the total time = O(log n) + O(log n) + O(log n) = 3 × O(log n)

Since constant factors are ignored in asymptotic analysis,
3 x O(log n )= O(log n).

The worst-case number of comparisons required to search an element in a bitonic array is Θ(log 𝑛).