---
round: 3
ticket_no: 25
source_no: 25
slug: binary-search
topic: Binary Search
difficulty: Easy
leetcode_id: 704
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 25 — Binary Search

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

Дан отсортированный по возрастанию массив целых чисел `nums` и целое число `target`. Если `target` присутствует в `nums`, верните его индекс. Иначе верните `-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
```

Constraints: `1 <= nums.length <= 10^4`; `-10^4 < nums[i], target < 10^4`; все элементы `nums` уникальны; массив отсортирован по возрастанию.

## Ответ

> Так как у нас массив отсортирован, мы можем использовать бинарный поиск. То есть мы ставим указатели на начало и конец нашего массива, рассчитываем средний индекс между ними, попадаем куда-то в серединку и смотрим, найден элемент или нет. Если там элемент больше, чем то, что мы ищем, это означает, что нам еще влево надо двигаться. А если меньше, то нам вправо нужно двигаться. То есть мы смещаем левый, правый вот эти диапазоны, сокращаем. Ну, бинарный поиск, одним словом.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

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

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

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