Java を使用した無限配列内の要素の検索-＆＃＆チュートリアル-php.cn

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

WBOY

リリース： 2024-09-11 12:30:29

オリジナル

968 人が閲覧しました

Finding an Element in an Infinite Array Using Java

問題提起

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

アプローチの概要

狭い範囲から開始します: 最初は、要素が狭い範囲内 (たとえば、インデックス 0 と 1 の間) にあると想定します。
範囲を動的に拡大します: ターゲット要素が最初の範囲で見つからない場合、範囲のサイズを 2 倍にしてさらに検索します。この指数関数的な増加により、ターゲットが存在する可能性のある範囲を素早く絞り込むことができます。
範囲内の二分探索: ターゲットを含む適切な範囲を決定したら、二分探索を適用してターゲットのインデックスを効率的に見つけます。

コード

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)。これにより、各反復でより多くの領域を効果的にカバーできるようになります。