Быстрые необязательные параметры в реализации бинарного поиска

Question

Я хочу написать хорошую реализацию бинарного поиска в Swift, и следующее выглядит как хак, чтобы преодолеть преодоление нижней и верхней границ во всех случаях.

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int? = 0, _ upperBound: Int? = 0) -> Int? {
    var ub = upperBound
    if (ub == 0 ) { ub = arr.count
}

Подробное объяснение: янаписал набор тестов в форме: XCTAssertEqual(binarySearch(arr: [1,2,3,4], target: 5), nil)

и я не хочу передавать нижнюю и верхнюю границу в двоичный поиск в первом случае.

Мой заголовок функции выглядит:

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int? = 0, _ upperBound: Int? = 0) -> Int? {

в каждом рекурсивном вызове бинарного поиска нижняя граница будет либо нулевой, либо переданным параметром, и это имеет смысл.Но верхняя граница не дает.

Теперь я хотел бы написать что-то вроде

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int? = 0, _ upperBound: arr.count) -> Int? {

, но, очевидно, это невозможно.

Я бы даже хотел добавитьследующее (но явно не может, так как upperBound является константой let):

if (upperBound == 0 ) {upperBound = arr.count}

Я бы хотел использовать:

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int? = 0, _ var upperBound: Int? = 0) -> Int? {

, но похоже, что это уже неособенность в swift.

Мне осталось использовать дополнительную переменную следующим образом, потому что это беспорядок!

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int? = 0, _ upperBound: Int? = 0) -> Int? {
    var ub = upperBound
    if (ub == 0 ) {ub = arr.count}

Answer 1

Это обычная ситуация. Для сигнатуры рекурсивной функции может потребоваться больше параметров, чем для ее точки входа. Лучший способ справиться с этим - использовать вложенную функцию.

func binarySearch(_ array: [Int], for target: Int) -> Int? {
    func binarySearch(_ array: [Int], for: Int, lowerBound: Int, upperBound: Int) -> Int? {
        // your implementation here
    }

    return binarySearch(array, for: target, lowerBound: 0, upperBound: array.count)
}

Чтобы получить больше кода Swifty, я предлагаю вам конвертировать, попробуйте использовать:

• Расширение, а не бесплатная функция, которая использует параметр для того, что фактически является "собой"
• Диапазон вместо 2 отдельных Int с
• Публичная точка входа с минимальными параметрами и закрытая рекурсивная функция будут иметь все необходимые параметры для рекурсии.

Вот пример для начала:

extension RandomAccessCollection where Self.IndexDistance == Int {
    public func binarySearch(for target: Element) -> Int? {
        return binarySearch(for: target, inRange: 0 ..< self.count)
    }

    private func binarySearch(for target: Element, inRange range: CountableRange<Int>) -> Int? {
        return nil // Your implementation here
    }
}

Answer 2

Я бы сделал параметр верхней границы необязательным (как вы), но установил бы значение по умолчанию nil.Затем вы создаете локальное значение ub как:

let ub = upperbound ?? arr.count

Нижняя граница должна быть необязательной со значением по умолчанию 0.

func binarySearch(arr: [Int], target: Int, _ lowerBound: Int = 0, _ upperBound: Int? = nil) -> Int? {
    let ub = upperBound ?? arr.count