Overview
Binary Search sorted array ko half-half cut karke target dhoondhta hai.
Analogy
Dictionary me word dhoondhne jaisa: beech kholo, left ya right decide karo, repeat karo.
Step-by-step
- low = 0 aur high = n - 1 se start karo.
- mid = (low + high) // 2 nikalo.
- Agar arr[mid] == target ho to mid return karo.
- Agar target chhota ho to high = mid - 1 karo.
- Warna low = mid + 1 karo, jab tak low <= high.
Visual
[1 3 5 7 9] -> mid 5 -> target bada -> right side -> 7 mil gaya.
Common mistakes
- low/high update ke baad mid dubara calculate nahi karna.
- while me < use karna instead of <=.
- mid = (low + high) kuch languages me overflow kar sakta hai.
Practice questions
- 7 elements wale array par present aur absent target ka trace banao.
- Not found case me insertion index return karo.
- Explain karo ki unsorted array par binary search kyu fail hoti hai.