Унифицированные массивы и массивы в Swift

Question

Я очень новичок в Swift и для программирования Apple в целом. Я написал этот код для двоичного поиска.

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

и я получил ошибки синтаксиса на рекурсивных вызовов, поскольку второй параметр имеет тип ArraySlice<X> вместо Array<X>.

Я имел дело с этим, перегружая binarySearch версией, которая идентична, за исключением того, что второй параметр имеет тип ArraySlice<X>.

Я думаю, что было бы более элегантно, если бы все могло быть сделано в одной функции. Есть ли подходящий тип, который объединяет как Array, так и ArraySlice? Я пробовал использовать ArrayLiteralConvertible<X>, но по какой-то причине у него нет счетчика. У меня все еще есть проблемы с поиском путей в документах, поэтому я могу легко упустить возможность выбора.

Можете ли вы предложить хороший способ сделать это? Если это связано с использованием встроенного класса, можете ли вы дать мне совет о том, как найти его для себя в следующий раз, вместо того, чтобы писать в SO?

Answer 1

Да, объект Array/ArraySlice вызывает раздражение. Основные общие требования, которые вам нужны, подробно описаны в вопросе this. Однако, чтобы получить ваши требования, к сожалению, вы должны получить довольно красивые отпечатки функций. Это является возможно, хотя:

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

И для Swift 1.2, просто поменять тело для этого:

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

Answer 2

Чтобы обойти вашу первоначальную проблему, вызовите 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])) 
    } 
} 

Кроме того, ваше состояние должно быть if needle < found.