python - 事前に並べ替えられた配列で指定された値の最小インデックスを見つける

Question

ねえ、私はインタビューでこの質問をして、それを解決する最善の方法は何だろうと思っていました. たとえば、すでにソートされている配列が与えられ、ある値 x の最小のインデックスを見つけたいとします。

これは私が思いついたもののpython /疑似コードです。それについてもっと良い方法があるかどうか疑問に思っていますか?

def findLowestIndex(arr, x):
     index = binarySearch(0, len(arr), x)
     if index != -1:
         while index > 0:
           if arr[index] == arr[index-1]:
              index -= 1
           else:
              break
     return index

ありがとう！

Answer 1

x配列内の s の数が O( n )の場合、メソッドは最悪の場合に線形時間を要します。

O(lg nx ) の解は、二分探索自体を変更して、配列のいずれか 1 つではなく最初のものを見つけることで取得できます。

def binary_search(x, a):
    lo = 0
    hi = len(a)

    while lo < hi:
        mid = (lo + hi) // 2

        if a[mid] < x:
            lo = mid + 1
        elif a[mid] > x:
            hi = mid
        elif mid > 0 and a[mid-1] == x:
            hi = mid
        else:
            return mid

    return -1

Answer 2

import bisect
l = [1,2,3,4,4,4,4,4,5,5,5,5,5,6,6,7,7,7,8,8]
bisect.bisect_left(l, 4)

編集：私は何かが恋しいです。二等分すると、挿入ポイントが表示されます。したがって、x がリストにない場合でも、結果のインデックスが表示されます。したがって、最初に x がリストにあるかどうかを確認する必要があります。

if x in l:
    ....

しかし、インタビューの質問では、ライブラリを使用する代わりに、どのようにアルゴリズムを考え出すかを見たいと思うかもしれません...

Answer 3

要素が整数または列挙されている場合は、少し速く実行できます。

二分探索 [Python 関数ではなくアルゴリズム] では、要素が存在しない場合、インデックスよりも大きい最小の要素を見つけることができることに注意してください。

1. 最初にx- を検索し、インデックスを取得しますi。
2. 次に、 を検索しx-1ます。リストにない場合は、二分検索で最初のインデックスを見つけることができますx。
3. リストにある場合は、見つかったインデックスを次のようにしますj。
   • jからまでのサブリストでバイナリ検索を実行し、次のiような要素を検索します。list[k] < list[k+1]

列挙されていない値の場合、範囲を縮小するという同じ考え方で行うこともできますが、list[k] < list[k+1] and list[k+1] == x最初に整数に対してどのように行われるかを理解し、次にそれを一般的な解決策に適用する方が簡単だと思います。

このソリューションは ですがO(logn)、あなたが提案する簡単なソリューションはO(n)であり、二分探索後の反復ステップのため、多くの重複があるリストにあることに注意してください。

Answer 4

誰かが興味を持っているなら、再帰的なバージョン...

https://github.com/reeargento/algorithms-sedgewick-wayne/blob/master/src/chapter1/section4/Exercise10.javaから書き直し、アルゴリズム 4thの演習です。

def binary_search(key, a, low, high):
    if low > high:
        return -1;
    middle = low + (high - low) / 2;
    if a[middle] < key:
        return binary_search(key, a, middle + 1, high)
    elif a[middle] > key:
        return binary_search(key, a, low, middle - 1)
    else:
        if (middle - 1 >= 0) and (a[middle - 1] != key):
            return middle
        else:
            index = binary_search(key, a, 0, middle - 1)
            if(index == -1):
                return middle;
            else:
                return index;

a = [1,2,3,3,3,3,4,5,6,7,7,8,9]

print(binary_search(7, a, 0, len(a)))

再帰的なバージョンは、非再帰的なバージョンよりも常に簡単に見えませんか? なぜこれはもっと難しく見えるのですか..？誰でもより良い再帰バージョンを書くことができます:D?

Answer 5

そうでxない場合、答えは簡単です。それを見つけるための二分探索です。Xf(x) = v

そのxようなものがあるf(x) = v場合、答えも簡単です。それを見つけるための二分探索です。

xこの問題は、そのようなものが複数ある場合にのみ興味深いものf(x) = vです。の数が一定xの場合、アルゴリズム的には二分探索が最適です。二分探索だけで、下位のインデックスを順番にチェックします。

しかし、これらの がたくさんある場合はどうxでしょうか? そのような順次検索は明らかに最適ではありません。実際、 がある場合c * |X| x、これは で実行されO(|X|)ます。

代わりに、 at に初期化lboundして0、要素 at が見つかるまで二分探索を行うことができます。ここでi、右に行くたびに、lbound使用したばかりの mid に更新します。次に、 から二分探索し[lbound, i - 1]ます。i == lbound要素が見つからなくなるまでこれを行います。前者が発生した場合、目的のインデックスは0です。後者が発生した場合、目的のインデックスは以前にi使用されたものです。最悪の場合、目的のインデックスは0です。

興味深いことに、これはまだ間に合いlog(|X|)ます。

Answer 6

二分探索における等価アプローチの遅延検出により、最小のインデックスが得られ、等価ブランチが削減されます。

def binary_search(low, high, target, array):
    while low < high:
        mid = low + (high - low) / 2
        if a[mid] < target:
            low = mid + 1
        else:
            high = mid

    if (array[low] == target) return low
    else return -1

Answer 7

gddc のコメントが python の最速の答えであることは間違いありません。それ以外の場合、場合によってはバイナリ検索の O(log n) 動作を打ち負かすことができるという事実を除いて、一般的なアルゴリズムは正しいです。具体的には、整数の場合、得られる最悪の場合の最良の動作は O(sqrt(log n)) です: https://stackoverflow.com/questions/4057258/faster-than-binary-search-for-ordered-リスト

Answer 8

二分探索を変更して、x の出現を初めて見つけます。