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. 参考ページ
8. 次回の記事