Поиск в списке
- Поиск означает определение того, содержится ли значение в списке, и где именно.
- Обычный ответ — индекс значения или
-1, если он отсутствует. - Два классических метода: линейный поиск и бинарный поиск.
Линейный поиск
- Проверяйте каждый элемент последовательно, начиная с начала.
- Остановитесь, как только найдете совпадение.
- Он работает с любым списком, отсортированным или нет.
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
Бинарный поиск
- Бинарный поиск требует отсортированного списка.
- Посмотрите на средний элемент. Если это целевое значение, остановитесь.
- Если целевое значение меньше, ищите в левой половине; если больше — в правой.
data = [2, 4, 6, 8, 10]
target = 8
low = 0
high = len(data) - 1
found = -1
while low <= high:
mid = (low + high) // 2
if data[mid] == target:
found = mid
break
elif data[mid] < target:
low = mid + 1
else:
high = mid - 1
print(found)
Сравните их
- Линейный поиск может проверить каждый элемент — медленно для длинного списка.
- Бинарный поиск отбрасывает половину списка на каждом шаге, поэтому он намного быстрее.
- Но бинарный поиск работает только тогда, когда данные уже отсортированы.
В псевдокоде Cambridge
- Обратите внимание, что
DIV— это целочисленное деление (аналог Python's//). - Массивы Cambridge обычно идут от 1 до
n, количества элементов.LENGTH()используется для строк, поэтому циклы используютn.
// Linear search — stop at the first match
found ← -1
i ← 1
WHILE i <= n AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 1
high ← n
WHILE low <= high AND found = -1
MiddleIndex ← (low + high) DIV 2
IF list[MiddleIndex] = target THEN
found ← MiddleIndex
ELSE
IF list[MiddleIndex] < target THEN
low ← MiddleIndex + 1
ELSE
high ← MiddleIndex - 1
ENDIF
ENDIF
ENDWHILE
Распространенные ошибки
- Бинарный поиск требует отсортированного списка; он сокращает диапазон вдвое на каждом шаге.
- Линейный поиск работает с любым списком, но медленнее.
Теперь попробуйте сами
- Верните индекс значения или
-1, если оно не найдено. - Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
Линейный против бинарного поиска
Бинарный поиск halves the list each step — far fewer comparisons.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Write linear_search(items, target) that отдачи the index of target in items, or -1 if it is not there. Check the items one by one.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Write binary_search(items, target) for a sorted list. Return the index of target, or -1 if it is missing. Halve the range each step.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
Write first_negative(items) that scans the list and отдачи the index of the first number less than 0, or -1 if there are none.
Нажмите Запустить, чтобы увидеть результат здесь.