# Binary Search — Data Structures और Algorithms: Interviews के लिए Patterns

Source: https://www.skillbyai.com/hi/dsa/binary-search

> Search space आधा करके sorted range में O(log n) में target खोजें, और off-by-one गलतियों से बचें।

## हर चरण में आधा हटाएँ

**Sorted** array पर, लक्ष्य की मध्य तत्व से तुलना करें। यदि लक्ष्य बड़ा है, तो पूरा left आधा (mid सहित) अप्रासंगिक — `left` को उससे आगे ले जाएँ। अन्यथा right आधा हटाएँ। हर चरण search स्थान आधा: `O(log n)`।

## Iterative टेम्पलेट

अन्य भाषाओं में overflow से बचने को `left <= right` और `mid = left + (right-left)//2` उपयोग करें।

```python
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1     # target in right half
        else:
            hi = mid - 1     # target in left half
    return -1
```

Output:

```
binary_search([10,20,30,40,50,60,70,80], 60) -> 5
```

## Dry run: 60 खोजें

`[10 20 30 40 50 60 70 80]`

- चरण 1: lo=0 hi=7 mid=3 → arr[3]=40 < 60 → lo=4
- चरण 2: lo=4 hi=7 mid=5 → arr[5]=60 → **इंडेक्स 5 पर मिला**

**Quiz:** Binary search के लिए डेटा होना चाहिए...

- [ ] Hash map में संग्रहीत
- [ ] अभाज्य लंबाई का
- [x] Sorted (या predicate पर monotonic)
- [ ] केवल धनात्मक संख्याएँ

*Answer:* Sorted (या predicate पर monotonic). आधा हटाना तभी काम करता है जब एक ओर लक्ष्य न होने की गारंटी हो — इसके लिए क्रम चाहिए।