# Binary Search

- **Canonical ID**: `binary-search`
- **Canonical URL**: https://dsacheatsheet.com/problems/binary-search
- **Difficulty**: easy
- **Patterns**: Binary Search
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/binary-search/

## 1. Core Invariant / The Trick

Closed interval `[l, r]` invariant: `while l <= r`, compute `mid = l + ((r - l) >> 1)` preventing 32-bit overflow, adjust `l = mid + 1` or `r = mid - 1`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(log N)`
- **Space Complexity**: `O(1)`
- **Proof**: Halves search space on each iteration.

## 3. Minimal Idiomatic Code

### Python
```python
def search(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1
    while l <= r:
        m = (l + r) // 2
        if nums[m] == target: return m
        if nums[m] < target: l = m + 1
        else: r = m - 1
    return -1
```

### TypeScript
```typescript
export function search(nums: number[], target: number): number {
  let l = 0, r = nums.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (nums[m] === target) return m;
    if (nums[m] < target) l = m + 1; else r = m - 1;
  }
  return -1;
}
```

### C++
```cpp
int search(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (nums[m] == target) return m;
        nums[m] < target ? l = m + 1 : r = m - 1;
    }
    return -1;
}
```

### Java
```java
int search(int[] nums, int target) {
    int l = 0, r = nums.length - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (nums[m] == target) return m;
        if (nums[m] < target) l = m + 1; else r = m - 1;
    }
    return -1;
}
```

### Go
```go
func search(nums []int, target int) int {
    l, r := 0, len(nums)-1
    for l <= r {
        m := l + (r-l)/2
        if nums[m] == target { return m }
        if nums[m] < target { l = m + 1 } else { r = m - 1 }
    }
    return -1
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Overflow on `(l + r) / 2` in C++/Java when indices approach `INT_MAX`.

### Follow-ups
- Lower bound / Upper bound invariants for handling duplicates (`l < r` with half-open `[l, r)`).