Swift: поиск ближайшего значения в массиве с помощью двоичного поиска - PullRequest
Новая
       17

Swift: поиск ближайшего значения в массиве с помощью двоичного поиска

2 голосов
/ 08 июля 2019

Я пытаюсь найти ближайшее значение в массиве, используя бинарный поиск.Все работает нормально, пока искомое значение не меньше, чем наименьшее значение в массиве.

К сожалению, отладчик не принес ничего полезного.Поэтому я прошу сообщество сейчас.Вы также можете попробовать код прямо на игровой площадке Xcode.Я попытался изменить другое искомое значение на меньшее значение, как в массиве, но получил ту же ошибку.Ошибка: ошибка: выполнение было прервано, причина: EXC_BAD_INSTRUCTION (код = EXC_I386_INVOP, субкод = 0x0). 

func closestValue(_ arr: [Int],_ target: Int) -> Int {
    var leftPointer = 0
    var rightPointer = arr.count-1

    while leftPointer < rightPointer {
        let middleIndex = (leftPointer + rightPointer) / 2
        let middleValue = arr[middleIndex]

        if middleValue == target {
            return middleValue
        }

        //Check for out of bounds error
        let leftIndex = middleIndex-1
        let leftValue = arr[leftIndex]

        if leftValue <= target && middleValue >= target {
            let leftDistance = abs(leftValue-target)
            let rightDistance = abs(middleValue-target)

            if leftDistance <= rightDistance {
                return leftValue
            } else {
                return middleValue
            }
        }
        if middleValue <= target {
            leftPointer = middleIndex+1
        } else {
            rightPointer = middleIndex
        }
    }
    guard let first = arr.first, let last = arr.last else {
        fatalError()
    }

    if target <= first {
        return first
    } else if target >= last {
        return last
    } else {
        fatalError()
    }
}
let first = [1,2,3,5,5,5,7,9,19,11] // 6 --> 5
let second = [1,2,3] // 8 --> 3
let third = [9, 10, 22, 59, 67, 72, 100] // 70 --> 72
let fourth = [100, 101, 102] //5 --> 100    => Heres the error

print(closestValue(first, 6))
print(closestValue(second, 8))
print(closestValue(third, 110))
print(closestValue(fourth, 5))

Я ожидал четвертый вывод 100. Поскольку 100 - это ближайшее к 5 значение в четвертом массиве.

1 Ответ

0 голосов
/ 08 июля 2019

Я вижу, вы вводите некоторые проверки границ, но они должны происходить в начале функции, а не в конце. Позвольте мне переписать всю функцию: 

func closestValue(_ arr: [Int],_ target: Int) -> Int {
    // Array must not be empty
    guard arr.count > 0 else { fatalError("Array must not be empty") }

    // If array has only 1 element, that element is the closest
    guard arr.count > 1 else { return arr[0] }

    // To use binary search, your array must be ever-increasing or ever-decreasing
    // Here, we require that the array must be ever-increasing
    for index in 1..<arr.count {
        if arr[index - 1] > arr[index] {
            fatalError("Array must be monotonous increasing. Did you forget to sort it?")
        }
    }

    // If the target is outside of the range of the array,
    // return the edges of the array
    guard arr.first! <= target else { return arr.first! }
    guard target <= arr.last! else { return arr.last! }

    // Now some actual searching
    var left = 0
    var right = arr.count - 1

    while left < right {
        if left == right - 1 {
            return abs(arr[left] - target) <= abs(arr[right] - target) ? arr[left] : arr[right]
        }

        let middle = (left + right) / 2
        switch arr[middle] {
        case target:
            return target
        case ..<target:
            left = middle
        default:
            right = middle
        }
    }

    fatalError("It should never come here")
}


let first = [1,2,3,5,5,5,7,9,11,19] // 6 --> 5
let second = [1,2,3] // 8 --> 3
let third = [9, 10, 22, 59, 67, 72, 100] // 70 --> 72
let fourth = [100, 101, 102] //5 --> 100

print(closestValue(first, 6))
print(closestValue(second, 8))
print(closestValue(third, 70))
print(closestValue(fourth, 5))

Некоторые заметки:

  • if left == right - 1 { ... } позволяет завершить цикл while. В противном случае целочисленное деление округлит middle вниз `влево ', что приведет к бесконечному циклу.
  • case ..<target - это короткая рука для «когда arr[middle] < target»
  • while всегда должен найти решение и вернуться изнутри, но я еще не проверил это полностью. Если вы найдете случай, когда он достигнет последнего fatalError, дайте мне знать.
  • В первом примере есть два ответа: 5 и 7 находятся на расстоянии 1 от target = 6.
...