Быстрый бинарный поиск провалился до последнего оператора возврата

Question

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

let numbersArray:[Int] = [1, 2, 3, 4, 6, 6, 6, 7, 7, 8, 9, 11, 13, 15, 17, 19, 20]

var first: Int = 0
var last: Int = numbersArray.count - 1

func binarySearch(array: [Int], number: Int) -> Int{

    if array.count == 0 {return -1}
    else if array.count == 1{
            if array[0] == number {return array[0]}

            else {return -1}
    }

    let arrayMiddle: Int = array.count / 2

    if number == array[arrayMiddle] {return array[arrayMiddle]}

    else if number > array[arrayMiddle]{
           first = arrayMiddle + 1
            print("first in number > middle \(first)")
           last = array.count - 1
            print("last in number > middle \(last)")
            let slice: [Int] = Array(array[first...last])
            binarySearch(array: slice, number: number)


    }
    else if number < array[arrayMiddle]{
            last = arrayMiddle - 1
            print("last in number < middle \(last)")
            first = 0
            print("first in number < middle \(first)")
            let slice: [Int] = Array(array[first...last])
            binarySearch(array: slice, number: number)
    }

    print("got to last case")
    return -1
}

Answer 1

Вы должны использовать switch и проверить свои 3 случая:

1. Значение находится после середины. Создайте фрагмент после середины и рекурсивно вызывайте этот фрагмент, возвращая результат этого вызова.
2. Значение - середина, верните средний индекс.
3. Значение перед серединой. Создайте фрагмент перед серединой и рекурсивно вызовите этот фрагмент, возвращая результат этого вызова.

Кроме того, я бы сделал это обобщение и расширение для RandomAccessCollection. Таким образом, вам не нужно превращать каждый ArraySlice в Array при вызове рекурсии. Другое преимущество заключается в том, что ArraySlice поддерживает индексы исходной коллекции, поэтому вам не нужно будет поддерживать их самостоятельно. Создавая новые Array экземпляры, вы отбрасываете это.

Наконец, вместо возврата -1 вы можете использовать Optional и вернуть nil, чтобы указать, что значение отсутствует в коллекции. Это довольно стандартный способ справиться с этим.

Моя реализация:

extension RandomAccessCollection {
  func binarySearch<T>(value: T) -> Self.Index? where
    T: Comparable, Self.Element == T {
      guard !self.isEmpty else { return nil }

      let middle = self.index(self.startIndex, offsetBy: self.count / 2)

      switch self[middle] {
      case ..<value:
        let next = self.index(after: middle)
        return self[next...].binarySearch(value: value)
      case value:
        return middle
      default:
        return self[..<middle].binarySearch(value: value)
      }
  }
}

Answer 2

Вы рекурсивно вызываете binarySearch, не возвращая результат, дважды.