# Binary Search

> Locate a value in a sorted array in O(log n) by halving the search window on every comparison — never scanning what you can eliminate.

- **Category**: Algorithms
- **Subcategory**: searching
- **Canonical URL**: https://designpattern.fyi/patterns/binary-search/

---

## Description
**Intent**: Exploit sorted order to eliminate half the remaining candidates on each comparison — reducing a 1-million-element search to roughly 20 comparisons.

**Context**: You have a sorted array and need fast lookups. Linear search scans every element — O(n) per query. Binary search uses the sorted order to cut the search space in half on every step.

**Solution**: Compare the target to the middle element. Equal → return the index. Target smaller → discard the right half, repeat on the left. Target larger → discard the left half, repeat on the right. Continue until found or the window collapses to empty.



## Use Cases
Searching sorted arrays where an O(n) scan is too slow. Static or infrequently modified datasets where the sorting cost is paid once. When you need O(log n) lookup without the memory overhead of a hash table.



## Implementation Example

```javascript
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // Found
    } else if (arr[mid] < target) {
      left = mid + 1; // Search right half
    } else {
      right = mid - 1; // Search left half
    }
  }

  return -1; // Not found
}

// Usage
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sortedArray, 7)); // 3
console.log(binarySearch(sortedArray, 10)); // -1
```



## Trade-offs


### Advantages

- O(log n) time — 1M elements requires ~20 comparisons

- No extra memory — operates in-place on the input array

- Simple to implement and reason about




### Considerations & Drawbacks

- Data must be sorted first — unsorted input requires an O(n log n) sort upfront

- Frequent insertions or deletions require re-sorting or a different data structure entirely

- Not suitable for linked lists — O(1) random access is required for midpoint lookup