Решение, которое вы показываете, не для проблемы, которую вы пытаетесь решить. В их контексте они могут проверить, не загрязнена ли какая-то группа городов тем, что они называют «экспериментом», и хотят знать, как мало экспериментов им нужно, чтобы точно определить, какие города k загрязнены. Это теоретическая ситуация и, скорее всего, подразумевается только как упражнение без применения в реальной жизни.
В действительности вы не можете проверить, содержит ли массив элемент менее чем за O (n) времени в худшем случае, если этот массив не имеет какой-либо структуры (например,сортируется). В частности, вы не можете проверить, содержит ли массив k элементов за O (k log n) время для k = o (n / log (n)) , потому что в этом случае k log n = o (n) . Это, конечно, также означает, что для константы k .
невозможно (но если k того же порядка, что и n , тогда O (k log n) становится O (n log n) , и тогда вы можете прибегнуть к сортировке массива).
Если ваш массив отсортирован, вы можете выполнить k бинарный поиск и достижение этой среды выполнения.