⚙️ Алгоритмы  ·  20 вопросов  ·  ~35 мин  ·  ⏱ Таймер 35:00  ·  Лёгкий  · 

Линейный и двоичный поиск

Поиск отличается не только скоростью. Иногда нужен первый индекс, иногда последний, иногда место вставки, а иногда ответ вообще не лежит в массиве — упорядочено лишь множество возможных значений. Тест проверяет контракты функций, границы полуинтервалов, повторы и монотонность предиката.

Отвечено: 0 из 20
⏱ --:--
0%
💡 Инструкция: Выбери один ответ из четырёх. В тесте 20 вопросов и 35 минут. После завершения откроются общий процент, четыре тематические шкалы, правильные ответы и пояснения.
Вопрос 1 из 20
Какой индекс вернёт функция?
Python
def find(a, x):
    answer = -1
    for i, value in enumerate(a):
        if value == x:
            answer = i
    return answer

print(find([4, 2, 7, 2, 9, 2], 2))
Вопрос 2 из 20
Какое значение i будет напечатано?
Python
a = [8, 5, 3, 7, 1]
x = 7
i = 0
while i < len(a) and a[i] != x:
    i += 1
print(i)
Вопрос 3 из 20
Как изменить линейный поиск, чтобы вернуть первое совпадение в массиве с повторами?
Вопрос 4 из 20
Какой результат вернёт функция при пустом списке?
Python
def contains(a, x):
    for value in a:
        if value == x:
            return True
    return False

print(contains([], 10))
Вопрос 5 из 20
Когда линейный поиск предпочтительнее предварительной сортировки с последующим двоичным поиском?
Вопрос 6 из 20
Какой индекс будет напечатан?
Python
a = [2, 5, 8, 12, 16, 23, 38]
x = 16
left, right = 0, len(a) - 1
while left <= right:
    mid = (left + right) // 2
    if a[mid] == x:
        break
    if a[mid] < x:
        left = mid + 1
    else:
        right = mid - 1
print(mid)
Вопрос 7 из 20
Почему цикл может не завершиться?
Python
while left < right:
    mid = (left + right) // 2
    if a[mid] < x:
        left = mid
    else:
        right = mid
Вопрос 8 из 20
Какое предусловие обязательно для обычного двоичного поиска по значениям?
Вопрос 9 из 20
Что вернёт функция для x=6?
Python
def search(a, x):
    left, right = 0, len(a)
    while left < right:
        mid = (left + right) // 2
        if a[mid] < x:
            left = mid + 1
        else:
            right = mid
    return left

print(search([1, 4, 4, 7, 9], 6))
Вопрос 10 из 20
Почему формула mid = left + (right-left)//2 исторически считалась безопаснее, чем (left+right)//2 в языках с ограниченными целыми?
mid=left+\left\lfloor\frac{right-left}{2}\right\rfloor
Вопрос 11 из 20
Какую позицию вернёт lower_bound?
Python
a = [1, 3, 3, 3, 6, 8]
x = 3
left, right = 0, len(a)
while left < right:
    mid = (left + right) // 2
    if a[mid] < x:
        left = mid + 1
    else:
        right = mid
print(left)
Вопрос 12 из 20
Какую позицию вернёт upper_bound?
Python
a = [1, 3, 3, 3, 6, 8]
x = 3
left, right = 0, len(a)
while left < right:
    mid = (left + right) // 2
    if a[mid] <= x:
        left = mid + 1
    else:
        right = mid
print(left)
Вопрос 13 из 20
Как через lower_bound и upper_bound получить число вхождений x в отсортированный массив?
count(x)=ub(x)-lb(x)
Вопрос 14 из 20
Какой диапазон индексов содержит все четвёрки?
Python
a = [2, 4, 4, 4, 4, 7]
left = 1
right = 5
print(left, right - 1)
Вопрос 15 из 20
Что вернёт lower_bound для x, который больше всех элементов массива длины n?
Вопрос 16 из 20
Какое минимальное x найдёт программа?
Python
def enough(x):
    return x * x >= 30

left, right = 0, 30
while left < right:
    mid = (left + right) // 2
    if enough(mid):
        right = mid
    else:
        left = mid + 1
print(left)
Вопрос 17 из 20
Что должно быть монотонным для двоичного поиска минимальной допустимой вместимости?
Python
def feasible(capacity):
    # можно ли распределить груз по не более чем k рейсам
    ...
Вопрос 18 из 20
Какие начальные границы разумны для минимальной грузоподъёмности, если все грузы положительны и их нужно перевезти по порядку?
Вопрос 19 из 20
Сколько проверок предиката нужно в худшем случае на диапазоне целых ответов от 0 до 1 000 000?
\lceil\log_2(1{,}000{,}001)\rceil=20
Python
# обычный двоичный поиск первой истинной позиции
Вопрос 20 из 20
Почему нельзя применять двоичный поиск по ответу, если предикат по мере роста x имеет вид false, true, false, true?

Ответьте на все 20 вопросов, чтобы получить результат

🔗 Встроить тест на свой сайт (iframe) ▼

Скопируйте код и вставьте в любое место на вашем сайте:

Также доступна прямая ссылка на embed-страницу