Searching · Поиск
Searching a list
- Searching means finding whether a value is in a list, and where.
- The usual answer is the index of the value, or
-1if it is missing. - Two classic methods are linear search and binary search.
Поиск в списке
- Поиск означает определение того, содержится ли значение в списке, и где именно.
- Обычный ответ — индекс значения или
-1, если он отсутствует. - Два классических метода: линейный поиск и бинарный поиск.
Linear search
- Check each item in turn, from the start.
- Stop as soon as you find a match.
- It works on any list, sorted or not.
Линейный поиск
- Проверяйте каждый элемент последовательно, начиная с начала.
- Остановитесь, как только найдете совпадение.
- Он работает с любым списком, отсортированным или нет.
names = ["Sam", "Mia", "Leo"]
target = "Mia"
found = -1
for i in range(len(names)):
if names[i] == target:
found = i
break
print(found)
Binary search
- Binary search needs a sorted list.
- Look at the middle item. If it is the target, stop.
- If the target is smaller, search the left half; if bigger, the right half.
Бинарный поиск
- Бинарный поиск требует отсортированного списка.
- Посмотрите на средний элемент. Если это целевое значение, остановитесь.
- Если целевое значение меньше, ищите в левой половине; если больше — в правой.
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)
Compare them
- Linear search may check every item — slow for a long list.
- Binary search throws away half the list each step, so it is much faster.
- But binary search only works if the data is already sorted.
Сравните их
- Линейный поиск может проверить каждый элемент — медленно для длинного списка.
- Бинарный поиск отбрасывает половину списка на каждом шаге, поэтому он намного быстрее.
- Но бинарный поиск работает только тогда, когда данные уже отсортированы.
In Cambridge pseudocode
- Note
DIVis whole-number division (Python's//).
В псевдокоде Cambridge
- Обратите внимание, что
DIV— это целочисленное деление (аналог Python's//).
// Linear search — stop at the first match
found ← -1
i ← 0
WHILE i < LENGTH(list) AND found = -1
IF list[i] = target THEN
found ← i
ENDIF
i ← i + 1
ENDWHILE
// Binary search (list must be sorted)
found ← -1
low ← 0
high ← LENGTH(list) - 1
WHILE low <= high AND found = -1
mid ← (low + high) DIV 2
IF list[mid] = target THEN
found ← mid
ELSE
IF list[mid] < target THEN
low ← mid + 1
ELSE
high ← mid - 1
ENDIF
ENDIF
ENDWHILE
Common mistakes
- Binary search needs a sorted list; it halves the range each step.
- Linear search works on any list but is slower.
Распространенные ошибки
- Бинарный поиск требует отсортированного списка; он сокращает диапазон вдвое на каждом шаге.
- Линейный поиск работает с любым списком, но медленнее.
Now you try
- Return the index of the value, or
-1when it is not found. - Press Check answer to test your code.
Теперь попробуйте сами
- Верните индекс значения или
-1, если оно не найдено. - Нажмите Check answer (Проверить ответ), чтобы протестировать свой код.
Linear vs binary search · Линейный против бинарного поиска
Binary search halves the list each step — far fewer comparisons. · Бинарный поиск делит список пополам на каждом шаге — значительно меньше сравнений.
Write linear_search(items, target) that returns the index of target in items, or -1 if it is not there. Check the items one by one. · Напишите функцию linear_search(items, target), которая возвращает индекс элемента target в списке items или значение -1, если он отсутствует. Проверяйте элементы поочерёдно.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
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. · Напишите функцию binary_search(items, target) для отсортированного списка. Верните индекс элемента target или значение -1, если он отсутствует. На каждом шаге делите диапазон пополам.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.
Write first_negative(items) that scans the list and returns the index of the first number less than 0, or -1 if there are none. · Напишите функцию first_negative(items), которая сканирует список и возвращает индекс первого числа, меньшего чем 0, или значение -1, если таких чисел нет.
Click Run to see the output here. · Нажмите Запустить, чтобы увидеть результат здесь.