# Binary Search — डेटा स्ट्रक्चर और एल्गोरिदम

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

> Sorted सीमा को हर चरण में आधा कर O(log n) में लक्ष्य खोजें।

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

**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 के लिए डेटा होना चाहिए...

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

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