---
title: Binary Search
difficulty: Easy
category: Binary Search
leetcode_id: 704
revision_count: 1
last_revision: 2026-09-12
---

# Binary Search

> **LeetCode:** [#704](https://leetcode.com/problems/binary-search/)
> **Сложность:** Easy
> **Категория:** Binary Search

## Условие

Дан отсортированный по возрастанию массив целых чисел `nums` и целое число `target`. Найти индекс `target` в массиве, если он там есть, иначе вернуть `-1`.

```
Input: nums = [-1,0,3,5,9,12], target = 9  →  Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2  →  Output: -1
```

## Ключевая идея

Делим отрезок поиска пополам на каждом шаге: сравниваем средний элемент с `target` и отбрасываем половину, где `target` заведомо не может быть. Массив обязан быть отсортирован — это условие применимости.

## Оценка сложности

- **Время:** O(log n)
- **Память:** O(1)

## Решение (Ruby)

```ruby
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def search(nums, target)
  left = 0
  right = nums.size - 1

  while left <= right
    mid = left + (right - left) / 2  # защита от переполнения

    if nums[mid] == target
      return mid
    elsif nums[mid] < target
      left = mid + 1
    else
      right = mid - 1
    end
  end

  -1
end
```

## Разбор на примере

```
Input: nums = [-1,0,3,5,9,12], target = 9

left=0, right=5, mid=2 (3) → 3 < 9 → left=3
left=3, right=5, mid=4 (9) → 9 == 9 → return 4

Result: 4
```

## Edge Cases

- `nums` пустой → сразу `-1`
- `nums` из одного элемента: может быть target или нет
- `target` меньше всех элементов → right уходит в -1, возвращаем -1
- `target` больше всех элементов → left уходит за границу, возвращаем -1
- Отрицательные числа в массиве — работают так же
- Переполнение `(left + right) / 2` при больших `left + right` — используем `left + (right - left) / 2`

## Типичные ошибки

- Условие `while left < right` вместо `left <= right` — пропускается последний элемент, когда `left == right`
- `mid = (left + right) / 2` — потенциальное переполнение в других языках, в Ruby не проблема, но хорошая привычка
- Забывают обновить `left = mid + 1` / `right = mid - 1`, а не `mid`, — бесконечный цикл
- Не проверяют, что массив отсортирован (не требуется — дано по условию)

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| **Классический binary search** | **O(log n)** | **O(1)** | **стандарт для интервью** |
| Linear scan | O(n) | O(1) | тривиально, но не пройдёт на собеседовании |
| Ruby built-in `Array#bsearch` | O(log n) | O(1) | можно упомянуть, но на интервью пишут руками |

### Ruby built-in

```ruby
nums.bsearch { |x| x >= target } == target
```

> **Важно:** `bsearch` требует отсортированного массива и возвращает элемент, а не индекс. Для индекса: `nums.bsearch_index { |x| x >= target }`.

## Заметки после повторения

_Что забыл? Что пошло не так? На чём застрял? Заполни после каждой тренировки._