# Binary search & boundary cases

Code With Purpose · Hinglish · Free starter lesson

## Concept

Binary search sorted data par kaam karta hai. Middle element ko target se compare karo, phir woh half hatao jahan target nahi ho sakta. Har step candidate positions ko lagbhag aadha karta hai.

Yahan low aur high inclusive bounds hain. Jab tak low <= high hai, target agar present hai toh isi interval mein hai. low = middle + 1 ya high = middle - 1 checked position ko hataata hai aur progress ensure karta hai. -1 ka matlab match nahi mila.

Indexable sequence ke liye search O(log n) comparisons leta hai aur iterative version mein extra space O(1) hai. Unsorted data ko sort karne ki cost alag hai. Duplicate values hon toh algorithm koi matching index deta hai, zaroori nahi first ho. Empty input, endpoints, absent target aur duplicates test karo.

## Example

```python
def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        middle = (low + high) // 2
        if values[middle] == target:
            return middle
        if values[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

print(binary_search([2, 5, 8, 12, 19], 12))
print(binary_search([], 12))
```

## Expected output

```text
3
-1
```

## Exercise

First aur last elements, aur missing target test karo. Kya [8, 2, 5] par directly function call karna sahi hai? Explain karo.

## Suggested solution

```
assert binary_search([2, 5, 8], 2) == 0
assert binary_search([2, 5, 8], 8) == 2
assert binary_search([2, 5, 8], 6) == -1
# [8, 2, 5] is unsorted: the algorithm's assumption is broken.
# Sort first if appropriate, noting that indices then refer to the sorted list.
```

## Takeaway

Algorithm tabhi correct hai jab uski assumptions hold karti hain.

Reference: https://docs.python.org/3/library/bisect.html

https://codewithpurposeai.in/lesson-dsa-binary-search.html?lang=hinglish