1. 記事の概要

LeetCodeのStudy Plan(Binary Search)では、一番最初の問題で公式解説を確認する事ができます。
当記事は、その解説を読みながら、自分なりに要点をまとめた備忘録です。
言語は、Swiftを想定しています。

2. 記事の結論

配列の両端をそれぞれ、left,rightに指定する。
midを求め、pivot pointと比較し、探索範囲を2分の1にする。
該当しなかった場合は、-1をreturnする(基本は、問題の指示に従うこと)

3. 課題

[Int]型のArray[-7,-4,-1,0,3,5,9,12]から、target=9を見つけてください。
該当しない場合は、-1をreturnしてください。

4. アプローチ1: 正確な値を見つける

4-1. leftとright

まず、[Int]型の任意の配列Arrayを用意します。
- この時、Arrayは、数字の小さいものから昇順に並び替えられているものとします。
配列のindexには必ず最初のindexと最後のindexが存在します。それを便宜的にleft, rightとします。
これにより、全てのindexは[left, right]の範囲内にあると考える事ができます。

//Array
[-7, -4, -1, 0, 3, 5, 9, 12]

//この際、left: -7、right: 12となる。

//よって、Arrayに格納されている全てのindexは-7　~ 12の範囲内に存在すると考えられる。

4-2. 探索方針

配列を探索するためには、forループやwhileを使うなどして、探索していくと賢明です。
その際、探索の終了条件を、要素がemptyであるかどうかを検知するべきでしょう。
それを検知するためには、whileを使い、条件式にleft<=rightを指定してあげるとよいです。
こうすることで、探索範囲が空だったり、left<=rightを満たさない条件が出現時に、loopが止まるはずです。

4-3. ピポットポイント(pivot point)の設定

次に検討することは、pivot pointを設定してあげることです。
pivot point（以下pivot）とは、探索範囲を2つに分割するための中間地点です。
pivotを設定したら、Arrayのmiddle indexとtargetの値を比較する必要があります。
- こうする事で、条件式に該当しない半分については、検索する必要がなくなるため、検索量を半減させることが出来るメリットがあります。
探索範囲が少ない競プロの問題だと、全探索ゴリ押しでもACを叩き出す事ができますが、検索量が増えて配列の要素数が1,000や10,000クラスになってくると、処理スピードが遅く、長くなってしまいますので、pivotを使って、探索範囲を削減していく必要があります。

4-4. 例外処理

arrayが以下のような場合に対応する必要があります。

var array: [Int] = [3]
// target = 9, No exact matches

var array: [Int] = [20]
// target = 9, No exact matches

ですので、該当しないArrayが登場した際にも対応できるように、コードを一文追加しましょう。

return -1

こうする事で、arrayの中にtargetが見つからなかった場合でも、エラーを吐かずにプログラムを実行させる事ができます。

5. コード全体

var left: Int = 0
var right: Int = 8

var array: [Int] = [-7,-4,-1,0,3,5,9,12]
var target: Int = 9

print(searchIndex())

func searchIndex() -> Int{
    var left = 0
    var right = nums.count - 1
    while left<=right {
        let mid = ( left + right ) / 2 

        // 正解
        if nums[mid] == target {
            return mid
        }

        // pivotよりtargetの方が大きい時
        if nums[mid] < target {
            // 答えはpivotよりright側にあるので、left側の探索を切る
            // mid + 1を　leftに代入することで、midより小さい配列のindexを検索しないようにする
            left = mid + 1
        }

        // pivotよりtargetの方が小さい時
        if nums[mid] > target {
            // 答えはpivotよりleft側にあるので、right側の探索を切る
            // mid - 1を　rightに代入することで、midより大きい配列のindexを検索しないようにする
            right = mid - 1
        }
    }

    return -1

}

6.最後に

何かご指摘事項などございましたら、コメント欄等でお知らせしていただけると幸いです。

7. 参考ページ

https://leetcode.com/problems/binary-search/solutions/2794222/binary-search/?envType=study-plan&id=binary-search-i

8. 次回の記事