Find First and Last Position of Element in Sorted Array
整数のリスト nums が与えられます。このリストは非減少順に並んでいるため、同じ値が繰り返し現れることがあります。また、整数 target も与えられます。0から数えた2つのインデックスのリストを返してください。target が最初に現れる位置と最後に現れる位置です。target がリストに含まれていない場合は、[-1, -1] を返してください。時間計算量は O(log n) を目指してください。
関数
- numsinteger-array
- 値が重複する場合もある、ソート済みの整数のリスト
- targetinteger
- 探す値
- 戻り値integer-array
- target の最初と最後のインデックス。見つからない場合は [-1, -1]
制約
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsは非減少順に並んでいます。
例
- 入力
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- 出力
- [1, 3]
- 説明
- 5の3つのコピーはインデックス1、2、3にあるため、この連続部分は1から始まり、3で終わります。インデックス0には3があり、インデックス4には8があるため、これ以上続きません。
- 入力
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- 出力
- [-1, -1]
- 説明
- 7 は、インデックス 3 の 5 とインデックス 4 の 8 の間に位置しますが、どちらも 7 ではありません。リストに 7 は含まれていないため、答えは
[-1, -1]です。
発展問題
同じリストに対して異なるターゲットの検索が何千回も行われる場合、あらかじめリストを1回走査しておけば、各検索をO(log n)より速くできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
numsはソートされているため、targetのすべての出現箇所は連続して並んでいます。その連続部分の両端を求める必要があります。同じ値の連続が長い場合、1つを見つけて外側へ順に調べると、
O(n)のコストがかかることがあります。代わりに、一致した後も左へ進み続けるように二分探索を変更します。すると、探している数以上の値を持つ最初のインデックスで停止します。nums[i] ≥ value를 만족하는 첫 번째 인덱스를 반환하는 도우미 함수를 하나 작성하세요.target을 인수로 호출해 구간의 시작을 구하고, 해당 위치의 값이target인지 확인한 다음,target + 1을 인수로 호출하세요. 구간은 그 인덱스보다 1 앞에서 끝납니다.
解説
通常の二分探索は、targetのコピーのうち最初に見つかったものを返しますが、そのコピーが連続範囲のどこにあるかは分かりません。代わりに、下限、つまり指定した数以上の値を持つ最初のインデックスを探します。targetとtarget + 1の下限を求めると、O(log n)で連続範囲の両端が得られます。
リスト全体を走査する
考え方
リストを一度走査します。targetが最初に見つかったインデックスが開始位置で、最後に見つかったインデックスが終了位置です。targetが一度も現れない場合、どちらも-1のままです。
これはソート済みかどうかにかかわらず、どんなリストでも使えますが、それが弱点でもあります。すべてのn個の値を読み取るからです。10^4個の値を含むリストでは、約28回で済むところ、10,000回の比較が必要になります。
アルゴリズム
first = last = -1を設定します。- 各インデックス
iについて、nums[i]がtargetと等しい場合、firstがまだ-1であればfirst = iを設定し、last = iを設定します。 [first, last]を返します。
def searchRange(nums, target):
first = last = -1
for i, value in enumerate(nums):
if value == target:
if first == -1:
first = i # the first match fixes the start
last = i # every later match moves the end
return [first, last]1つコピーしてから、展開する
考え方
targetを含む任意のインデックスを二分探索します。リストはソートされているため、そのインデックスの周辺では、すべてのコピーが途切れないひと続きの範囲にあります。隣の値がまだtargetである間、左右に進みます。
探索の計算量はO(log n)で、コピーごとに1ステップずつ進むため、合計でkステップです。リストの大部分がtargetの場合、たとえば10^4個のコピーがあると、すべての値を読み取ることになり、線形探索と変わらなくなります。
アルゴリズム
nums[found] == targetとなる任意のインデックスfoundを二分探索で見つけます。- 見つからない場合は、
[-1, -1]を返します。 - その前の値が
targetと等しい間、foundからfirstを左に移動します。 - その後の値が
targetと等しい間、foundからlastを右に移動します。 [first, last]を返します。
def searchRange(nums, target):
# An ordinary binary search finds some copy of target, if there is one.
lo, hi = 0, len(nums) - 1
found = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
found = mid
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
if found == -1:
return [-1, -1]
# The copies sit next to each other, so walk out to both ends of the run.
first = last = found
while first > 0 and nums[first - 1] == target:
first -= 1
while last < len(nums) - 1 and nums[last + 1] == target:
last += 1
return [first, last]2つの下限二分探索
考え方
別の問いを考えます。値が少なくとも value である最初のインデックスはどれでしょうか。そのような値がなければ、そのインデックスは下限、または n です。常にそのインデックスを含む半開区間 [lo, hi) を維持します。nums[mid] < value なら、mid とそれより前のすべての値は小さすぎます。それ以外の場合、mid は条件を満たしますが、より前のインデックスも条件を満たす可能性があるため、新しい hi として mid を範囲内に残します。一致してもループは早期終了しません。
target の下限は、その連続部分の始まりです。値は整数なので、target より大きい最初の値は target + 1 の下限にあり、その連続部分はその1つ前のインデックスで終わります。最初の例では、5の下限は1、6の下限は8がある4です。つまり、連続部分は [1, 3] です。連続部分の長さにかかわらず、10^4 個の値に対する2回の検索にかかるステップ数は約28です。
アルゴリズム
lowerBound(value)を記述します。lo = 0、hi = nから始めます。lo < hiの間、nums[mid] < valueならlo = mid + 1を設定し、そうでなければhi = midを設定します。loを返します。first = lowerBound(target)を設定します。first == nまたはnums[first] != targetの場合、[-1, -1]を返します。last = lowerBound(target + 1) - 1を設定し、[first, last]を返します。
def lowerBound(nums, value):
# The first index whose number is at least value, or len(nums) if none is.
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < value:
lo = mid + 1 # nums[mid] and everything before it is too small
else:
hi = mid # nums[mid] qualifies, but an earlier index might too
return lo
def searchRange(nums, target):
first = lowerBound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
# The run of target ends right before the first number above target.
last = lowerBound(nums, target + 1) - 1
return [first, last]
落とし穴と境界ケース
nums[mid] == targetになった時点ですぐに返す。返されるインデックスは、その連続範囲内のどこにでもなり得る。[3, 5, 5, 5, 8]では、最初の中央のインデックスは 2 で、どちらの端でもない。nums[mid] ≥ valueのとき、下限探索でhi = mid - 1と書く。これでは答えかもしれないmidを除外してしまう。first < nを確認せずにnums[first]を読み取る。例にある 13 のように、targetがすべての値より大きい場合、下限はnとなり、末尾の次の位置を指す。- Lua と R では位置のずれを忘れないこと。リストは 1 から始まるため、両方の位置から 1 を引く。
よくある質問3
最初と最後の位置を見つける時間計算量はどれくらいですか？
2 回の二分探索で、時間計算量は O(log n)、空間計算量は O(1) です。どちらの探索も一致しても停止しないため、処理コストは対象の値が何個あるかに依存しません。10^4 個の値の場合、各探索は約 14 ステップです。
二分探索における下限とは何ですか？
値の下限は、その値以上の要素がある最初のインデックスです。該当する要素がない場合は、リストの長さになります。リストをソートされた状態に保つために、その値を挿入する位置です。上限は、その値より厳密に大きい要素がある最初のインデックスです。
1つの二分探索関数で、最初のインデックスと最後のインデックスの両方を見つけられますか？
はい。検索にフラグを持たせます。一致したときはインデックスを記録し、最初の要素を見つけるには左へ、最後の要素を見つけるには右へ検索を続けます。target と target + 1 に対して下限検索を呼び出す方法もあります。どちらも O(log n) で実行できます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def searchRange(nums, target):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
期待される出力
[1, 3]