cari
RumahJavajavaTutorialMencari Elemen dalam Tatasusunan Tak Terhingga Menggunakan Java

Finding an Element in an Infinite Array Using 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  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!

Kenyataan
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Rangka Kerja 4 JavaScript teratas pada tahun 2025: React, Angular, Vue, SvelteRangka Kerja 4 JavaScript teratas pada tahun 2025: React, Angular, Vue, SvelteMar 07, 2025 pm 06:09 PM

Artikel ini menganalisis empat kerangka JavaScript teratas (React, Angular, Vue, Svelte) pada tahun 2025, membandingkan prestasi, skalabilitas, dan prospek masa depan mereka. Walaupun semuanya kekal dominan kerana komuniti dan ekosistem yang kuat, popul mereka yang relatif

Bagaimanakah saya melaksanakan caching pelbagai peringkat dalam aplikasi java menggunakan perpustakaan seperti kafein atau cache jambu?Bagaimanakah saya melaksanakan caching pelbagai peringkat dalam aplikasi java menggunakan perpustakaan seperti kafein atau cache jambu?Mar 17, 2025 pm 05:44 PM

Artikel ini membincangkan pelaksanaan caching pelbagai peringkat di Java menggunakan kafein dan cache jambu untuk meningkatkan prestasi aplikasi. Ia meliputi persediaan, integrasi, dan faedah prestasi, bersama -sama dengan Pengurusan Dasar Konfigurasi dan Pengusiran PRA Terbaik

Spring Boot Snakeyaml 2.0 CVE-2022-1471 Isu TetapSpring Boot Snakeyaml 2.0 CVE-2022-1471 Isu TetapMar 07, 2025 pm 05:52 PM

Artikel ini menangani kelemahan CVE-2022-1471 dalam Snakeyaml, kecacatan kritikal yang membolehkan pelaksanaan kod jauh. Ia memperincikan bagaimana peningkatan aplikasi boot musim bunga ke snakeyaml 1.33 atau lebih lama mengurangkan risiko ini, menekankan bahawa kemas kini ketergantungan

Bagaimanakah mekanisme kelas muatan Java berfungsi, termasuk kelas yang berbeza dan model delegasi mereka?Bagaimanakah mekanisme kelas muatan Java berfungsi, termasuk kelas yang berbeza dan model delegasi mereka?Mar 17, 2025 pm 05:35 PM

Kelas kelas Java melibatkan pemuatan, menghubungkan, dan memulakan kelas menggunakan sistem hierarki dengan bootstrap, lanjutan, dan pemuat kelas aplikasi. Model delegasi induk memastikan kelas teras dimuatkan dahulu, yang mempengaruhi LOA kelas tersuai

Node.js 20: Peningkatan Prestasi Utama dan Ciri -ciri BaruNode.js 20: Peningkatan Prestasi Utama dan Ciri -ciri BaruMar 07, 2025 pm 06:12 PM

Node.js 20 dengan ketara meningkatkan prestasi melalui penambahbaikan enjin V8, terutamanya pengumpulan sampah yang lebih cepat dan I/O. Ciri -ciri baru termasuk sokongan webassembly yang lebih baik dan alat penyahpepijatan halus, meningkatkan produktiviti pemaju dan kelajuan aplikasi.

Iceberg: Masa Depan Jadual Data TasikIceberg: Masa Depan Jadual Data TasikMar 07, 2025 pm 06:31 PM

Iceberg, format meja terbuka untuk dataset analitik yang besar, meningkatkan prestasi data dan skalabiliti. Ia menangani batasan parket/orc melalui pengurusan metadata dalaman, membolehkan evolusi skema yang cekap, perjalanan masa, serentak w

Cara berkongsi data antara langkah -langkah dalam timunCara berkongsi data antara langkah -langkah dalam timunMar 07, 2025 pm 05:55 PM

Artikel ini meneroka kaedah untuk berkongsi data antara langkah -langkah timun, membandingkan konteks senario, pembolehubah global, lulus argumen, dan struktur data. Ia menekankan amalan terbaik untuk mengekalkan, termasuk penggunaan konteks ringkas, deskriptif

Bagaimanakah saya dapat melaksanakan teknik pengaturcaraan berfungsi di Java?Bagaimanakah saya dapat melaksanakan teknik pengaturcaraan berfungsi di Java?Mar 11, 2025 pm 05:51 PM

Artikel ini meneroka mengintegrasikan pengaturcaraan berfungsi ke dalam Java menggunakan ekspresi Lambda, API Streams, rujukan kaedah, dan pilihan. Ia menyoroti faedah seperti kebolehbacaan dan kebolehkerjaan kod yang lebih baik melalui kesimpulan dan kebolehubahan

See all articles

Alat AI Hot

Undresser.AI Undress

Undresser.AI Undress

Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover

AI Clothes Remover

Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Undress AI Tool

Undress AI Tool

Gambar buka pakaian secara percuma

Clothoff.io

Clothoff.io

Penyingkiran pakaian AI

AI Hentai Generator

AI Hentai Generator

Menjana ai hentai secara percuma.

Alat panas

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Muat turun versi mac editor Atom

Muat turun versi mac editor Atom

Editor sumber terbuka yang paling popular

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Persekitaran pembangunan bersepadu PHP yang berkuasa

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Dreamweaver Mac版

Dreamweaver Mac版

Alat pembangunan web visual