---
round: 1
ticket_no: 11
source_no: 25
slug: binary-search
topic: Binary Search
difficulty: Easy
leetcode_id: 704
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-12
---

# Билет 11 — Binary Search

## Условие (как предъявлено)

Дан отсортированный по возрастанию массив целых чисел `nums` и целое число `target`. Нужно вернуть индекс `target` в массиве или `-1`, если его нет. Требуемая сложность — `O(log n)`.

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

## Ответ

> Так как у нас возрастающая отсортированная последовательность, значит, нам здесь доступен бинарный поиск. То есть мы ставим диапазон поиска: сначала это левая сторона — это начало нашего массива, а правая сторона — это конец. Берем серединку из него, рассчитываем индекс и проверяем: элемент, сравниваем, который фактически там стоит, с тем, который нам нужно найти. Если он оказался тем, что нужно, всё, мы нашли его. Если, например, он больше, чем нам нужно. Если он больше, ну, короче, туда мы понимаем, в какой диапазон дальше идти. Если больше, значит, нам надо еще меньше. Мы в левый, значит, идем, где поменьше значения. Вот там мы ищем. То есть мы сдвинули правую границу, и теперь там ищем. И так далее. Мы сужаем каждый раз, пока не наткнемся. Ну и может оказаться, что диапазон схлопнется, то есть у нас все левый и правый элементы соприкасаются, а ответа всё ещё нет, но это означает, что его нет, он начнется один.

## Разбор

**Что верно:** диапазон l..r, середина, сравнение с target и отбрасывание половины, выход по схлопыванию диапазона — верно.

**Что упущено и ошибки:** граница цикла названа нечётко: нужен while l <= r, иначе на массиве из одного элемента ответ теряется; не названа сложность O(log n) / O(1); граничные случаи: пустой массив, target вне диапазона.

**Эталонная идея:** l = 0, r = n-1; while l <= r: mid = (l + r) / 2; сравнить; сдвинуть l или r; вернуть -1.

**Сложность:** время O(log n), память O(1)

**Критерии:** идея ✅ · структура данных ✅ · сложность ❌ · граничные случаи ⚠️


**Разбор задачи:** [`../../algo-solutions/02-extra/04-binary-search/25-binary-search.md`](../../algo-solutions/02-extra/04-binary-search/25-binary-search.md)