Java を使用した無限配列内の要素の検索

問題提起

ソートされた整数の無限配列が与えられた場合、指定されたターゲット数値のインデックスを見つける必要があります。配列は「無限」です。つまり、そのサイズを事前に決定できないため、従来の二分探索を直接適用することはできません。

アプローチの概要

1. 狭い範囲から開始します: 最初は、要素が狭い範囲内 (たとえば、インデックス 0 と 1 の間) にあると想定します。

2. 範囲を動的に拡大します: ターゲット要素が最初の範囲で見つからない場合、範囲のサイズを 2 倍にしてさらに検索します。この指数関数的な増加により、ターゲットが存在する可能性のある範囲を素早く絞り込むことができます。

3. 範囲内の二分探索: ターゲットを含む適切な範囲を決定したら、二分探索を適用してターゲットのインデックスを効率的に見つけます。

コード

public class InfiniteArraySearch {
    public static void main(String[] args) {
        // Define the array (for demonstration purposes, treat this as infinite)
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};  
        int target = 6;

        // Call the function to find the target element
        int result = findElementInInfiniteArray(arr, target);
        System.out.println("Element found at index: " + result);
    }

    // Function to find the target in the infinite array
    static int findElementInInfiniteArray(int[] arr, int target) {
        // Start with a small range
        int start = 0;
        int end = 1;

        // Dynamically increase the range until the target is within bounds
        while (target > arr[end]) {
            int newStart = end + 1;  // Update start to one after the current end
            end = end + (end - start + 1) * 2;  // Double the range
            start = newStart;  // Move the start to newStart
        }

        // Perform binary search within the determined range
        return binarySearch(arr, target, start, end);
    }

    // Standard binary search implementation
    static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target < arr[mid]) {
                end = mid - 1;  // Move the end to the left
            } else if (target > arr[mid]) {
                start = mid + 1;  // Move the start to the right
            } else {
                return mid;  // Element found
            }
        }
        return -1;  // Element not found
    }
}

コードの説明

1. メイン関数

main 関数は、サンプル配列 arr とターゲット値 6 を定義します。簡単にするために、ここでは配列が有限であると仮定しますが、概念的にはそれを無限として扱います。次に、メイン関数は findElementInInfiniteArray を呼び出してターゲットを検索し、見つかった場合はインデックスを出力します。

2.範囲拡張（探索範囲を直線的に拡大する）

findElementInInfiniteArray メソッド内:

• 要素が [0, 1] の範囲内にあると仮定することから始めます。
• ターゲットが arr[end] の値より大きい場合、ターゲットが現在の範囲内にないことを意味します。したがって、範囲を 2 倍にすることで指数関数的に拡張します (end = end + (end - start + 1) * 2)。これにより、各反復でより多くの領域を効果的にカバーできるようになります。

3. 二分探索

ターゲットが開始と終了の間にある必要があることがわかったら、標準の二分探索を実行します。二分検索は、各ステップで検索スペースが半分に削減されるため、ソートされた配列内で検索する効率的な方法です。主な比較は次のとおりです:

• ターゲットが中央の要素 (arr[mid]) より小さい場合は、左半分を検索します。
• ターゲットが大きい場合は、右半分を検索します。
• ターゲットが中央の要素と一致する場合、そのインデックスを返します。

4. エッジケース

• ターゲットが配列内の最小要素より小さい場合、または配列にターゲットがまったく含まれていない場合、アルゴリズムは -1 を返します。

時間計算量

1. 範囲拡張: 反復ごとに範囲が 2 倍になるため、ターゲットが存在する正しい範囲を見つけるには O(log N) 回の操作が必要です。

2. 二分検索: 範囲が見つかると、二分検索は O(log M) で実行されます。ここで、M は範囲のサイズです。

したがって、全体の時間計算量は約 O(log N + log M) となります。

以上がJava を使用した無限配列内の要素の検索の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。