Ilustrasi prinsip dan pelaksanaan carian binari algoritma klasik Java

Artikel ini membawa anda pengetahuan yang berkaitan tentang java Kaedah separuh carian juga dipanggil carian binari, seperti namanya, ia membahagikan data kepada dua bahagian, dan kemudian menentukan separuh daripada kunci itu found. , dan kemudian ulangi langkah di atas sehingga kunci sasaran ditemui.

Pembelajaran yang disyorkan: "tutorial video java"

Carian binari

Carian binari juga dipanggil carian separuh ( Carian Binari), iaitu kaedah carian yang lebih cekap yang boleh melengkapkan carian dalam kerumitan masa logaritma skala data. Ia adalah algoritma carian untuk mencari elemen tertentu dalam tatasusunan tertib.

Idea algoritma

Ambil urutan menaik sebagai contoh, bandingkan saiz elemen sasaran dan elemen di tengah jujukan, jika elemen sasaran lebih besar daripada elemen dalam tengah, teruskan ke separuh kedua urutan Lakukan carian binari dalam; jika elemen sasaran lebih kecil daripada elemen di kedudukan tengah, bandingkan separuh pertama tatasusunan jika ia sama, kedudukan elemen ditemui . Panjang tatasusunan untuk setiap perbandingan ialah separuh daripada tatasusunan sebelumnya sehingga kedudukan elemen yang sama ditemui atau elemen sasaran tidak ditemui.

Ilustrasi

Diberi tatasusunan tertib dalam nombor tertib menaik=[-1, 0, 2, 5, 8, 12, 18, 38, 43, 46]

Kemudian cari sasaran nilai sasaran = 12 dalam tatasusunan.

Rajah adalah seperti berikut:

Dekat dengan soalan asal

Portal

Perihalan tajuk:

Memandangkan nombor tatasusunan integer (menaik) elemen tersusun dan sasaran nilai sasaran, tulis fungsi untuk mencari sasaran dalam nombor dan kembalikan subskrip jika nilai sasaran wujud, jika tidak, kembalikan -1.

Contoh 1:

Input: nums = [-1,0,3,5,9,12], sasaran = 9
Output: 4
Penjelasan : 9 muncul dalam nombor dan subskrip ialah 4

Contoh 2:

Input: nums = [-1,0,3,5,9,12] , sasaran = 2
Output: -1
Penjelasan: 2 tidak wujud dalam nombor, jadi ia mengembalikan -1

Idea penyelesaian:

Mengikut maksud soalannya, kita dapat ini Tatasusunan ialah tatasusunan tertib, yang juga merupakan prasyarat untuk menggunakan carian binari.

• Tentukan dua penunjuk yang menunjuk ke elemen pertama dan terakhir tatasusunan; sasaran berada dalam tatasusunan pada separuh masa kedua, jika tidak
berada pada separuh masa pertama;
• mengulangi langkah sebelumnya sehingga
• , menunjukkan bahawa sasaran ditemui dan subskrip dikembalikan. nums[mid] de0a15e4ba2b60513706903419a798b0 target
Pelaksanaan kod Java:
• nums[mid] = target
Analisis kerumitan:

Kerumitan masa: O(logn), dengan n ialah panjang tatasusunan .

class Solution {
    public int search(int[] nums, int target) {
        int left = 0,right = nums.length - 1;
        while(left <= right) { // 循环条件
            int mid = left + (right - left) / 2;
            if(nums[mid] == target){
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;  // 找不到则返回-1
    }
}

Kerumitan ruang: O(1).

• Pembelajaran yang disyorkan: "
tutorial video java
• "

Atas ialah kandungan terperinci Ilustrasi prinsip dan pelaksanaan carian binari algoritma klasik Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!