補間検索アルゴリズム

補間検索の定義

The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Binary Search always goes to the middle element to check. On the other hand, interpolation search may go to different locations according to the value of the key being searched. For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.

• www.geeksforgeeks.org

スペースの複雑さ

補間検索の空間複雑度は O(1)

補間検索の時間計算量

最良の場合
平均的なケース
最悪の場合


O(1)
O(log2(log2 n))
の上)

補間検索式

補間検索の式は次のとおりです.pos = low + ((x – A[low]) * (high – low) // (A[high] – A[low]))私のように、この数式をどのように取得したかを尋ねられた場合は、この驚くべき article by Hitesh Kumar をチェックしてください

補間検索のアルゴリズム

上記の式を使用して位置を計算する

array[pos] == wantedElement の場合: pos

を返す

array[pos] > wantedElement の場合: high = pos - 1

array[pos] < wantedElement の場合: low = pos + 1

は、array[pos] == wantedElement またはサブアレイがゼロになるまで繰り返します.

pythonを使った補間検索の実装

def InterpolationSearchAlgorithm(wantedItem: int, sortedItems: list):
    """
        => Algorithm Name: Interpolation search
        => Algorithm Type: search algorithms
        => Time Complexity: 
            [best case]     => O(1)
            [average case]  => O(log2(log2 n))
            [worst case]    => O(n)
        => Space Complexity => O(1)
        => Algorithm
            [1] =>  calculating the pos using the formula above
            [2] =>  if `array[pos] == wantedElement`: return pos
            [3] =>  if `array[pos] > wantedElement` : `high = pos - 1`
            [4] =>  if `array[pos] < wantedElement` : `low = pos + 1`
            [5] =>  stay repeating until the `array[pos] == wantedElement` or the sub-array reduces to zero.
        => params
            (wantedItem) => int
            (sortedItems) => sorted list and equally distributed.
        => Returns 
            (index) if the wanted item exists in the sortedItems
            (False) if the wanted item doesn't exist 
    """
    low = 0 
    high = len(sortedItems) - 1
    while (high >= low and sortedItems[high] >= wantedItem and sortedItems[low] <= wantedItem):
        # formula of interpolation sort
        pos = low + ((high - low) // (sortedItems[high] - sortedItems[low]) *
                    (wantedItem - sortedItems[low]))

        if sortedItems[pos] == wantedItem:
            # if it match return his index (pos)
            return pos
        elif sortedItems[pos] < wantedItem:
            # if A[pos] is smaller than wantedItem
            low = pos + 1
        else:
            # if A[pos] is larger than wantedItem
            high = pos - 1
    return False

リファレンスと役立つリソース

https://www.techiedelight.com/interpolation-search/

https://medium.com/@smellycode/demystifying-interpolation-formula-for-interpolation-search-211780c43269

https://www.geeksforgeeks.org/interpolation-search/

https://en.wikipedia.org/wiki/Interpolation_search#:~:text=Interpolation%20search%20is%20an%20algorithm,by%20W.%20W.%20Peterson%20in%201957.

#day_7
すてきな一日を!