Swift 二分探索

二分探索とは

ソート済みの配列から特定の値を探し出す時に二分割しながら探しだすアルゴリズムのこと。
メリットは
データの量が増えても、大きく探す時間が変わらない。
探しているデータがどれでも、見つかるまでの時間が同じくらい等

探したい要素のインデックスを取ってくる場合

おかし.swift

//①index(of:)で探す
let okashiArray:[String] = [🍭, 🍰, 🍦, 🍫, 🍬]
okashiArray.index(of:"🍫")//３

//②　for文で回す
 func linearSearch<T: Equatable>(_ array: [T], _ key: T) -> Int? {
    for i in 0 ..< array.count {
        if array[i] == key {
            return i
        }
    }
    return nil
}
linerSearch(okashiArray,"🍫") //3

//③　二分探索（バイナリツリー）
func binarySearch<T: Comparable>(_ array: [T], key: T, range: Range<Int>) -> Int? {
    if range.lowerBound >= range.upperBound {
        return nil
      //中身がないのでnilを返す
    } else {
        // 真ん中のインデックス番号を取ってくる  
       //upperBound →　範囲の最大を取ってくる 例　  print((0..<3).upperBound)→３（注意　２じゃない）
      //lowerBound→　範囲の最小を取ってくる　　　　　例　  print((0..<3).lowerBound)→0
        let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2

        // 左側の方に値があるかどうか（小さいかどうか）
        if array[midIndex] > key {
　　　　　　　　　　　　　　　　//存在したら左側の配列を入れ直して再帰処理をする
            return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)

        // 右側の方に値があるかどうか（大きいかどうか）
        } else if array[midIndex] < key {
       ////存在したら右側の配列を入れ直して再帰処理をする
            return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)

        // どっちも当てはまらなければ真ん中にあるということなのでreturnする
        } else {
            return midIndex
        }
    }
}

//補足 
//Comparable→オブジェクトのもつプロパティで比較できるようにしてくれるプロトコル　Equatableであることが前提
//Equatable→　オブジェクト同士が等しいかどうかを調べる事ができるようにしてくれるプロトコル

binarySearch(okashiArray, key: "🍫", range: 0 ..< okashiArray.count)//3