Bagaimana untuk melaksanakan lelaran dalam carian binari java

1. Konsep Lelaran

Pelaksanaan berulang set arahan atau langkah tertentu dipanggil lelaran. Dalam istilah orang awam, panggil mereka satu persatu.

Perkara yang melaksanakan fungsi mengira masa lalu dipanggil iterator.

2. Tiga elemen lelaran

1. sekurang-kurangnya Terdapat pembolehubah yang secara langsung atau tidak terus menyimpulkan nilai baru daripada nilai lama Pembolehubah ini adalah pembolehubah lelaran.

2. Wujudkan hubungan

Apa yang dipanggil perhubungan berulang merujuk kepada formula (atau hubungan) bagaimana untuk memperoleh nilai seterusnya pembolehubah daripada sebelumnya nilai. Penubuhan hubungan berulang adalah kunci untuk menyelesaikan masalah berulang, yang biasanya boleh dicapai dengan menggunakan penaakulan rekursi atau ke belakang.

3. Kawalan proses

Bilakah proses berulang ini harus dipertimbangkan semasa menulis program berulang. Proses berulang tidak boleh dibiarkan berulang tanpa henti. Kawalan proses lelaran biasanya boleh dibahagikan kepada dua situasi: satu ialah bilangan lelaran yang diperlukan ialah nilai tertentu dan satu lagi ialah bilangan lelaran yang diperlukan tidak dapat ditentukan. Untuk kes terdahulu, bilangan gelung tetap boleh dibina untuk mengawal proses lelaran untuk kes kedua, syarat untuk menamatkan proses lelaran perlu dianalisis dengan lebih lanjut.

3. Contoh lelaran carian binari

/*非递归的折半查找*/
public static int binarySearch(int[] a, int x) {
int left = 0;
int right = a.length - 1;
while(left <= right) {
int mid = (left+ right) / 2;
if(x > a[mid]) {
left = mid+1;
} else if(x < a[mid]) {
right = mid-1;
} else {
return mid;
}
}
return -1;
}

Semua kerja dalam kos gelung O(1) untuk setiap lelaran, jadi analisis perlu menentukan bilangan gelung . Gelung bermula di kanan-kiri=leng-1 dan berakhir di kanan-kiri<= -1. Selepas setiap kitaran, nilai kanan-kiri adalah sekurang-kurangnya separuh daripada nilai sebelum kitaran; oleh itu, bilangan maksimum kitaran ialah [log(n-1)]+2. Oleh itu: masa berjalan ialah O(log N), manakala kerumitan masa rekursif memerlukan O(N).

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan lelaran dalam carian binari java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!