Поиск: линейный и бинарный
Поиск значения
- Частая задача — поиск: есть ли значение в массиве и где именно?
- Обычный ответ — индекс, где оно было найдено, или
-1, если его нет. - Мы изучаем два способа: линейный поиск (работает с любым массивом) и бинарный поиск (требует отсортированного массива, но работает значительно быстрее).
Линейный поиск
- Просмотрите каждый элемент от индекса
0до конца. - Если элемент равен целевому, верните его индекс немедленно.
- Если цикл завершился без совпадений, верните
-1.
public class Main {
public static void main(String[] args) {
int[] a = {4, 8, 15, 16, 23};
int target = 15;
int found = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] == target) {
found = i;
break; // stop early, we have it
}
}
System.out.println(found); // 2
}
}
Как быстро работает линейный поиск?
- В худшем случае (значение находится последним или отсутствует) он проверяет каждый элемент.
- Для списка из
nэлементов это составляет доnпроверок. Мы называем это линейным временем. - Для малых массивов это вполне приемлемо. Для огромных отсортированных массивов можно сделать лучше.
Бинарному поиску нужен отсортированный массив
- Бинарный поиск работает только тогда, когда массив уже отсортирован (по возрастанию).
- Он проверяет средний элемент, а на каждом шаге отбрасывает половину массива.
- Это намного быстрее: миллион элементов требует около 20 проверок, а не миллион.
Идея бинарного поиска
- Держите две границы:
low(начало) иhigh(конец). - Посмотрите на средний индекс
mid = (low + high) / 2. - Если
a[mid]равно целевому значению, вернитеmid. - Если
a[mid]слишком мало, цель находится справа, поэтому установитеlow = mid + 1. - Если
a[mid]слишком велико, цель находится слева, поэтому установитеhigh = mid - 1. - Остановитесь, когда
lowпревыситhigh; тогда значение отсутствует, верните-1.
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12, 16, 23, 38}; // sorted!
int target = 16;
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1; // go right
} else {
high = mid - 1; // go left
}
}
System.out.println(found); // 4
}
}
Когда значение отсутствует
- Оба поиска возвращают
-1, если цель не найдена в массиве. - Для бинарного поиска цикл завершается, когда
low > high— границы пересеклись, и искать больше негде. - Всегда обрабатывайте случай
-1в коде, вызывающем поиск.
public class Main {
public static void main(String[] args) {
int[] a = {2, 5, 8, 12}; // sorted
int target = 7; // not in the array
int low = 0;
int high = a.length - 1;
int found = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] == target) {
found = mid;
break;
} else if (a[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println(found); // -1
}
}
Распространенные ошибки
- Бинарному поиску нужен отсортированный массив.
- Линейный поиск — O(n); бинарный — O(log n).
Теперь попробуйте сами
- Каждая задача заранее заполняет каркас класса — напишите свой код внутри main или дополните показанный метод.
- Используйте Check answer (Проверить ответ), чтобы скомпилировать ваш код с предоставленными тестами и посмотреть результаты. Сохраните интерфейс класса и метода, показанный в стартере.
- Ваш код компилируется и выполняется на сервере, поэтому даже первый запуск происходит быстро.
Линейный против бинарного поиска
Бинарный поиск на каждом шаге уменьшает диапазон вдвое — проверок значительно меньше.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Допишите linearSearch(int[] a, int target). Верните индекс первого элемента, равного target, или -1, если его нет в массиве. Проверяйте элементы начиная с индекса 0 и выше.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Допишите binarySearch(int[] a, int target) для отсортированного массива. Используйте границы low/high и проверяйте средний элемент на каждом шаге. Верните индекс ⟨target⟩ или -1, если он отсутствует.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Допишите countOccurrences(int[] a, int target), которая возвращает количество повторений ⟨target⟩ в ⟨a⟩ (линейный поиск). Верните 0, если она никогда не встречается.
Нажмите Запустить, чтобы увидеть результат здесь.