当前位置: 动力学知识库 > 问答 > 编程问答 >

Unify Arrays and Array Slices in Swift

问题描述:

I'm very new to Swift, and to Apple programming in general. I wrote this code to do a binary search.

func binarySearch<X:Comparable> (needle:X, haystack:[X])->X? {

if haystack.isEmpty { return nil }

let mid = haystack.count / 2

let found = haystack[mid]

if found == needle {

return needle

}

else if found < needle {

return binarySearch(needle, haystack[0..<mid])

}

else {

return binarySearch(needle, haystack[mid+1..<haystack.count])

}

}

and I got syntax errors on the recursive calls because the second parameter is of type ArraySlice<X> instead of Array<X>.

I dealt with this by overloading binarySearch with a version that is identical except that the second parameter is of type ArraySlice<X>.

I think it would be more elegant if it could all be done in one function. Is there a suitable type that unifies both Array and ArraySlice? I tried using ArrayLiteralConvertible<X> but for some reason that doesn't have a count member. I still have a bit of trouble finding my way around in the docs, so I may easily have overlooked a better choice.

Can you suggest a good way to do this? If it involves using a built-in class, can you perhaps give me a tip on how to find it for myself next time, instead of writing to SO?

网友答案:

Yeah, the Array/ArraySlice thing is annoying. The basic generic requirements you need are detailed in this question. To get your requirements, though, unfortunately you've got to get some pretty hideous function signatures. It is possible, though:

func bSearch<
  S : Sliceable where S.SubSlice : Sliceable,
  S.SubSlice.Generator.Element == S.Generator.Element,
  S.SubSlice.SubSlice == S.SubSlice,
  S.Generator.Element : Comparable,
  S.Index : IntegerArithmeticType,
  S.Index : IntegerLiteralConvertible,
  S.SubSlice.Index == S.Index
  >(el: S.Generator.Element, list: S) -> S.Generator.Element? {

    if list.isEmpty { return nil }

    let midInd = list.endIndex / 2

    let midEl: S.Generator.Element = list[midInd] // type inference giving me some bugs here

    if midEl == el {
      return el
    }

    return midEl < el ?
      bSearch(el, list: list[midInd+1..<list.endIndex]) :
      bSearch(el, list: list[0..<midInd])
}

And for Swift 1.2, just swap out the body for this:

if isEmpty(list) { return nil }

let midInd = list.endIndex / 2

let midEl: S.Generator.Element = list[midInd] // type inference giving me some bugs here

if midEl == el {
  return el
}

return midEl < el ?
  bSearch(el, list[midInd+1..<list.endIndex]) :
  bSearch(el, list[0..<midInd])
网友答案:

To get around your initial problem, call the Array constructor with your slice to get an array:

func binarySearch<X:Comparable> (needle:X, haystack:[X])->X? {
    if haystack.isEmpty { return nil }
    let mid = haystack.count / 2
    let found = haystack[mid]
    if found == needle {
        return needle
    }
    else if needle < found {
        return binarySearch(needle, Array(haystack[0..<mid]))
    }
    else {
        return binarySearch(needle, Array(haystack[mid+1..<haystack.count]))
    }
}

Also, your condition should be if needle < found.

分享给朋友:
您可能感兴趣的文章:
随机阅读: