Вопрос проверяет понимание эффективности алгоритмов поиска в отсортированных данных.
Бинарный поиск в отсортированном массиве имеет сложность O(log n). Линейный поиск — O(n), но он не использует преимущества сортировки.
1. Бинарный поиск:
Делит массив пополам на каждом шаге.
Работает только с отсортированными данными.
2. Пример на Swift:
func binarySearch(_ array: [Int], _ target: Int) -> Int? {
var low = 0
var high = array.count - 1
while low <= high {
let mid = (low + high) / 2
if array[mid] == target { return mid }
else if array[mid] < target { low = mid + 1 }
else { high = mid - 1 }
}
return nil
}Вывод:
Для отсортированных данных всегда используйте бинарный поиск.
