CUET PG 2021 — Computer PYQ

Binary Search algorithm ki complexity ka detailed solution niche diya gaya hai:

Question

The complexity of binary search algorithm is?

---

Solution

Binary Search algorithm ki complexity niche di gayi hai:

• Worst-case Time Complexity: $O(\log n)$

   

• Average-case Time Complexity: $O(\log n)$

• Best-case Time Complexity: $O(1)$

   

• Space Complexity: $O(1)$ (Iterative approach ke liye)

   

---

Explanation (Mathematical Derivation)

Binary Search "Divide and Conquer" strategy par kaam karta hai. Har step mein search space (array size) aadha ho jata hai.

 

Maana ki array ka initial size $n$ hai:

1. Pehle step ke baad size hoga: $n/2$

2. Doosre step ke baad size hoga: $n/4=n/2^2$

3. Teesre step ke baad size hoga: $n/8=n/2^3$

4. $k$ steps ke baad size hoga: $n/2^k$

Worst case tab hota hai jab hum aakhri element tak pahunchte hain, yani jab size $1$ ho jata hai:

Dono taraf $\log$ (base 2) lene par:

Isliye, comparison ki total sankhya (steps) $k={\log }_{2}n$ hoti hai.

Summary:

Binary Search ki efficiency iski logarithmic complexity $O(\log n)$ ki wajah se hoti hai, jo ise Linear Search ($O(n)$) ke muqable bahut fast banati hai.