Алгоритмические задачи по Swift

Бинарный поиск (Binary Search) - это эффективный алгоритм для поиска значения в отсортированном массиве. Принцип алгоритма очень прост. Мы всегда имеем дело с упорядоченным массивом. Это позволяет прибегать к хитрости - на каждой итерации цикла, который мы запускаем, мы вычисляем индекс среднего элемента. Этот элемент сравниваем с искомым. Если элемент из середины массива оказался меньше, чем тот, что мы ищем, значит нужный нам находится правее по массиву, ведь массив упорядочен. Соответственно, нам нужно перейти в следующую итерацию цикла, "оставляя" ей лишь правую часть массива - в ней снова будет найден средний элемент и алгоритм повторится. Если же элемент из середины массива оказался больше искомого, то мы переходим к следующей итерации, отбрасывая правую часть массива, а оставляя левую. Если же элемент совпадает с искомым, мы выходим из цикла. func binarySearch(array: [T], key: T) -> Int? { var lowerBound = 0 var upperBound = array.count - 1 while lowerBound <= upperBound { let mid = (lowerBound + upperBound) / 2 if array[mid] == key { return mid } else if array[mid] < key { lowerBound = mid + 1 } else { upperBound = mid - 1 } } return nil } Термины: target - искомое значение index - индекс искомого значения. left, right - левый и правый индексы, определяющие область нахождения. mid - индекс элемента в центре текущего поля поиска, который будет сравниваться с целевым значением. Эта реализация основана на использовании цикла и позволяет найти индекс искомого фрагмента в отсортированном массиве или вернуть nil, если искомое значение не найдено.

Постановка: У Swift есть набор предопределенных операторов для арифметических и логических действий. Он также позволяет создавать свои собственные операторы, как унарные, так и бинарные. Определите и реализуйте собственный оператор возведения в степень ^^ по следующим требованиям: - принимает в качестве параметров два Int - возвращает результат возведения первого параметра в степень второго - корректно обрабатывает порядок алгебраических операций - игнорирует возможные ошибки переполнения Решение: Создание нового оператора происходит в два этапа: объявление и реализация. Объявление использует ключевое слово operator для задания типа (унарный или бинарный), для задания последовательности символов нового оператора, его ассоциативности и старшинства выполнения. Здесь оператор — это ^^ и его тип infix (бинарный). Ассоциативность правая. В Swift нет предопределенного старшинства для возведения в степень. В алгебре возведение в степень должно вычисляться перед умножением/делением. Таким образом, мы создаем пользовательский порядок выполнения, помещая возведение в степень выше умножения. Это объявление: precedencegroup ExponentPrecedence { higherThan: MultiplicationPrecedence associativity: right } infix operator ^^: ExponentPrecedence Это реализация: func ^^(base: Int, exponent: Int) -> Int { let l = Double(base) let r = Double(exponent) let p = pow(l, r) return Int(p) }

Вариант 1: extension Array where Element: Comparable { func countUniques() -> Int { let sortedValues = sorted() let initial: (Element?, Int) = (.none, 0) let reduced = sortedValues.reduce(initial) { ($1, $0.0 == $1 ? $0.1 : $0.1 + 1) } return reduced.1 } } Вариант 2: func countUniques<T: Hashable>(_ array: Array<T>) -> Int { return Set(array).count }

Постановка: Этот код сортирует массив по алфавиту. Максимально упростите замыкание. var animals = ["fish", "cat", "chicken", "dog"] animals.sort { (one: String, two: String) -> Bool in return one < two } print(animals) Решение: Swift автоматически определяет тип параметров замыкания и возвращаемый тип, так что вы можете убрать их: animals.sort { (one, two) in return one < two } Вы можете заменить имена параметров использованием нотации $i: animals.sort { return $0 < $1 } Замыкания, состоящие из одного оператора, могут не содержать ключевое слово return. Значение последнего выполненного оператора становится возвращаемым результатом замыкания: animals.sort { $0 < $1 } Наконец, так как Swift знает, что элементы массива соответствуют протоколу Equatable, вы можете просто написать: animals.sort(by: <) Есть и более короткий вариант: animals.sort() Он сортирует по возрастанию, работает для типов, реализующих Comparable.