ちょっとアルゴニズム - Binary Search

raywenderlich/swift-algorithm-club

基本のアルゴニズムです。配列の中の特定の数字を探します。このアルゴニズムの条件としては小さいものから大きいものへと並び替えが終わっているというのがあります。

Binary Searchの前に単純に配列の中の数字を探してみます。linearSearchと呼ばれるものです。

func linerSearch<T:Comparable>(_ list:[T],_ key:T)->Int?{
   for i in 0..<list.count{
       if key == list[i]{
           return i
       }
   }
   return nil
}

<T:Comparable>ですが、Genericの定義です。protocolの"Comparable"で比較することとができるようになります。

->Int?

をつけることで"return"が使えるようになります。

あとはfor-in loopで数字を探します。

基本はこの形で、今回テーマのBinary Searchを書いていきます。

linearSearchでは配列の前から"for-in loop"で探します。Binary Searchはというと"Binary "ということで配列を2分していくことで、早く見つけることを目的としています。linearSearchが"for-in loop"で前から順番探すに対してBinary Searchで"While"を使って2分割できる間(配列の先頭より最後尾の数字が大きい間)で真ん中の数字と探す数字と比較することで見つけていきます。

Binary Searchは分割していく時に配列の真ん中の数字を取得して、その真ん中の数字と、探す数字の一致を持って探索が終わります。

func binarySerch<T:Comparable>(_ list:[T],key:T)->Int?{
   var low = 0
   var tail = list.count
   
   while low < tail{
       let mid = (low + tail/2
       if list[mid] == key{
           return mid
       }else if list[mid] < key{
           low = mid + 1
       }else{
           tail = mid
       }
   }
   return nil
}

以下の"while"が肝となります。

while low < tail{
       let mid =(low + tail/2
       if list[mid] == key{
           return mid
       }else if list[mid] < key{
           low = mid + 1
       }else{
           tail = mid
       }
   }

let mid = (low + tail/2

で条件(low < tail)の中で半分にし続けます。lowとtailの値は探す数字で変わります。あとは

if list[mid] == key{}

で数字を見つけ出します。

見つけられなければ

else if list[mid] < key{
       low = mid + 1
}else{
       tail = mid
}

で、探す数字の方が大きければ、真ん中より右の方にあるため左端lowをmid+1にずらします。小さければtail = mid( 最後の数字を真ん中にします)にします。

わかりにくいので、

 [1,2,4,6,7,8]

があり、探す数字が"7"の場合は、mid(インデックス)は

3 > 5 > 4

のように変化していきます。

インデックスに対する数字は

6 > 8(6より右) > 7(8より左)

というふうに探していき、"7"を探し当てて、答えとしてはインデックスの"4"が出てきます。