1. 記事の概要
- LeetCodeのStudy Plan(Binary Search)では、一番最初の問題で公式解説を確認する事ができます。
- 当記事は、その解説を読みながら、自分なりに要点をまとめた備忘録です。
- 言語は、Swiftを想定しています。
1-1. 前回の記事
2. 記事の結論
- UpperBound/LowerBoundのどちらを採用するかを決める。
- (array[mid] == targetの場合)、UpperBoundならmid+1を、LowerBoundならmid-1を返す。
3. 課題
- 昇順に並んだ[Int]型のArray[-7,-4,3,9,9,9,12]から、target=9をinsertすべき場所を出力してください。
4. アプローチ2: 上界/下界を見つける
4-1. 前回のおさらい
- まず、[Int]型の任意の配列Arrayを用意します。
- この時、Arrayは、数字の小さいものから昇順に並び替えられているものとします。
- 配列のindexには必ず最初のindexと最後のindexが存在します。それを便宜的にleft, rightとします。
- これにより、全てのindexは[left, right]の範囲内にあると考える事ができます。
//Array
[-7,-4,3,9,9,9,12]
//この際、left: -7、right: 12となる。
//よって、Arrayに格納されている全てのindexは-7 ~ 12の範囲内に存在すると考えられる。
4-2. 探索方針
- こういうケースの場合、2つの方法が考えられます。
- finding the upper bound(以下Upper)
- finding the lower bound(以下Lower)
- Upperは、可能な限り右端に挿入する。
- Lowerは、可能な限り左端に挿入する。
//Example
var target = 9
var upperArray: [Int] = [-7,-4,3,9,9,9,12]
var lowerArray: [Int] = [-7,-4,3,9,9,9,12]
- upperArrayだと、targetを[9,12]の間に、lowerArrayだと[3,9]の間にtargetを入れようとするイメージです。
4-3. ピポットポイント(pivot point)の設定(おさらい)
- 次に検討することは、pivot pointを設定してあげることです。
- pivot point（以下pivot）とは、探索範囲を2つに分割するための中間地点です。
- pivotを設定したら、Arrayのmiddle indexとtargetの値を比較する必要があります。
- こうする事で、条件式に該当しない半分については、検索する必要がなくなるため、検索量を半減させることが出来るメリットがあります。
- 探索範囲が少ない競プロの問題だと、全探索ゴリ押しでもACを叩き出す事ができますが、検索量が増えて配列の要素数が1,000や10,000クラスになってくると、処理スピードが遅く、長くなってしまいますので、pivotを使って、探索範囲を削減していく必要があります。
4-4. 例外処理
コードを一文追加しましょう。
return -1
5. コード全体
5-1. コード全体(UpperBound)
var left: Int = 0
var right: Int = 8
var nums: [Int] = [-7,-4,3,9,9,9,12]
var target: Int = 9
print(searchIndex())
func searchIndex() -> Int{
while (left < right) {
var mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
if (left > 0 && nums[left - 1] == target) {
return left - 1;
}
return -1;
}
5-2. コード全体(LowerBound)
var left: Int = 0
var right: Int = 8
var array: [Int] = [-7,-4,3,9,9,9,12]
var target: Int = 9
print(searchIndex())
func searchIndex() -> Int{
while (left < right) {
var mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
if (left < nums.count && nums[left] == target) {
return left;
}
return -1;
}
6.最後に
- 何かご指摘事項などございましたら、コメント欄等でお知らせしていただけると幸いです。