Mencari Elemen dalam Tatasusunan Tak Terhingga Menggunakan Java

Pernyataan Masalah

Memandangkan tatasusunan integer diisih yang tidak terhingga, kita perlu mencari indeks nombor sasaran yang diberikan. Tatasusunan ialah "tak terhingga", bermakna kita tidak boleh menentukan saiznya terlebih dahulu, jadi kita tidak boleh menggunakan carian binari tradisional secara langsung.

Gambaran Keseluruhan Pendekatan

1. Mulakan dengan julat yang kecil: Pada mulanya, anggap elemen itu terletak dalam julat yang kecil (katakan, antara indeks 0 dan 1).

2. Tingkatkan julat secara dinamik: Jika elemen sasaran tidak ditemui dalam julat awal, kami menggandakan saiz julat untuk mencari lebih lanjut. Pertumbuhan eksponen ini membolehkan kami dengan cepat mengasah julat di mana sasaran mungkin ditempatkan.

3. Carian binari dalam julat: Setelah kami menentukan julat yang sesuai yang mengandungi sasaran, kami menggunakan carian binari untuk mencari indeks sasaran dengan cekap.

Kod

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
    }
}

Penjelasan Kod

1. Fungsi Utama

Fungsi utama mentakrifkan arr tatasusunan contoh dan nilai sasaran 6. Untuk kesederhanaan, kami menganggap tatasusunan adalah terhingga di sini, tetapi dari segi konsep, kami menganggapnya sebagai tak terhingga. Fungsi utama kemudian memanggil findElementInInfiniteArray untuk mencari sasaran dan mencetak indeks jika ditemui.

2. Peluasan Julat (Meluaskan Kawasan Carian Secara Linear)

Dalam kaedah findElementInInfiniteArray:

• Kita mulakan dengan mengandaikan bahawa elemen terletak dalam julat [0, 1].
• Jika sasaran lebih besar daripada nilai pada arr[end], ini bermakna sasaran tidak berada dalam julat semasa. Jadi, kami mengembangkan julat secara eksponen dengan menggandakannya (akhir = akhir + (akhir - mula + 1) * 2). Ini secara berkesan membolehkan kami merangkumi lebih banyak perkara dalam setiap lelaran.

3. Carian Binari

Setelah kami tahu bahawa sasaran mesti terletak di antara permulaan dan akhir, kami melakukan carian binari standard. Carian binari ialah cara yang cekap untuk mencari dalam tatasusunan yang disusun, kerana ia mengurangkan ruang carian sebanyak separuh pada setiap langkah. Perbandingan utama ialah:

• Jika sasaran kurang daripada elemen tengah (arr[pertengahan]), cari bahagian kiri.
• Jika sasaran lebih besar, cari separuh kanan.
• Jika sasaran sepadan dengan elemen tengah, kembalikan indeksnya.

4. Kes Tepi

• Jika sasaran lebih kecil daripada elemen terkecil dalam tatasusunan, atau jika tatasusunan tidak mengandungi sasaran sama sekali, algoritma akan mengembalikan -1.

Kerumitan Masa

1. Peluasan Julat: Julat berganda dengan setiap lelaran, jadi ia memerlukan operasi O(log N) untuk mencari julat yang betul di mana sasaran terletak.

2. Carian Perduaan: Setelah julat ditemui, carian binari dijalankan dalam O(log M), dengan M ialah saiz julat.

Oleh itu, kerumitan masa keseluruhan adalah lebih kurang O(log N + log M).

Atas ialah kandungan terperinci Mencari Elemen dalam Tatasusunan Tak Terhingga Menggunakan Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!