CODEWITHSUNDEEP
swift
noobsmcgoobs
noobsmcgoobs

Reputation: 2746

Swift Binary Search Falling Through to last return statement

I am trying to implement binary search in Swift 4. The code seems to work, except that the code is falling through to the last return statement. I tried putting it in an else clause but get a compiler warning saying that control reaches end of non-void. I want it so if the conditions are met, that the code will return early and not exit with the -1 value of the last return statement. 

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
}

Upvotes: 2

Views: 390

Answers (2)

user887210
user887210

Reputation:

You should use a switch and test against your 3 cases:

  1. The value is after the middle. Create a slice after the middle and recursively call into that slice, returning the result of that call.
  2. The value is the middle, return the middle index.
  3. The value is before the middle. Create a slice before the middle and recursively call into that slice, returning the result of that call.

Also, I would make this generic and an extension on RandomAccessCollection. That way you don't need to turn each ArraySlice into an Array when you call the recursion. The other advantage is that ArraySlice maintains the indices of the original collection so you won’t need to maintain them yourself. By creating new Array instances you’re throwing that away.

Lastly, instead of returning a -1 you might want to use an Optional and return nil to indicate that the value is not in the collection. That's a fairly standard way to handle it.

My implementation:

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)
      }
  }
}

Upvotes: 1

Tim Vermeulen
Tim Vermeulen

Reputation: 12562

You're recursively calling binarySearch without returning the result, twice.

Upvotes: 1

Related Questions