Overview
Binary Search sorted array को बार-बार आधा करके target ढूंढता है।
Analogy
जैसे dictionary में शब्द खोजना: बीच से खोलो, बाएं या दाएं जाओ, फिर दोहराओ।
Step-by-step
- low = 0 और high = n - 1 से शुरू करें।
- mid = (low + high) // 2 निकालें।
- अगर arr[mid] == target हो तो mid return करें।
- अगर target छोटा है तो high = mid - 1 करें।
- वरना low = mid + 1 करें; जब तक low <= high हो तब तक दोहराएं।
Visual
[1 3 5 7 9] -> mid=5 -> target बड़ा है -> दाईं तरफ -> 7 मिला।
Common mistakes
- low/high बदलने के बाद mid दुबारा calculate नहीं करना।
- loop में < लगाना, जिससे आखिरी element miss हो सकता है।
- mid = (low + high) overflow कर सकता है; low + (high - low) // 2 बेहतर है।
Practice questions
- 7 elements वाले sorted array पर present और absent target का trace बनाएं।
- target न मिले तो insertion index return करने वाला version लिखें।
- बताएं कि unsorted array पर binary search क्यों fail होती है।