swift-algorithm-clubです。

まず、リニアサーチ(線形探索)。

func linerserch(_ arry:[Int], _ key:Int) -> Int?{
    for i in 0..<arry.count{
        if key == arry[i]{
            print("答えは \(i) です")
        }
    }
 return nil
}

let numbers = [11, 59, 3, 2, 53, 17, 31, 7, 19, 67, 47, 13, 37, 61, 29, 43, 5, 41, 23]

linerserch(numbers, 3)

答えは 2 です

とコンソールに出ます。

コードをSwiftらしくしていきます。

func linerserch2(_ arry:[Int],_ key:Int) -> Int?{
   for (index,object) in arry.enumerated() where key == object{
      print("答えは \(index) です")
   }
   return nil
}

enumrate()を使っていますね。

通常は組込関数を使ってやれば一瞬ですが頭の体操ですね。

numbers.index(of:3)

そして、バイナリサーチ。(ソート済み出ないと実行できません)

func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
   if range.lowerBound >= range.upperBound {
       return nil
   } else {
       //　まず、配列の中心の値（index）を決めます。
       let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
       
　　　　// もし、左側に調べている値があれば、さらに左側を再帰呼び出しで調べます。
       if a[midIndex] > key {
           return binarySearch(a, key: key, range: range.lowerBound ..< midIndex)
       
　　　　// もし、右側にあれば右側を右側を再帰呼び出しで調べます。
       } else if a[midIndex] < key {
           return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
       
　　　　// もし、同じ値であればそれが求める配列のインデックス
       } else {
           return midIndex
       }
   }
}

let numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]
binarySearch(numbers, key: 43, range: 0 ..< numbers.count) 

とすると、答えは13とでる。

配列を2分割し続けて真ん中の数に調べる値が合致するまで再帰関数で調べていきます。

Whileを使う方法も、

func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
   var lowerBound = 0
   var upperBound = a.count

   while lowerBound < upperBound {
       let midIndex = lowerBound + (upperBound - lowerBound) / 2
       if a[midIndex] == key {
           return midIndex
       } else if a[midIndex] < key {
           lowerBound = midIndex + 1
       } else {
           upperBound = midIndex
       }
   }
   return nil
}