Carian tatasusunan linear
Selalunya anda perlu mencari nilai yang diberikan dalam tatasusunan atau laporan bahawa ia tidak ada di sana. Untuk melakukan ini, anda perlu melihat semua elemen tatasusunan dari yang pertama hingga yang terakhir. Sebaik sahaja elemen yang sama dengan nilai yang diberikan X ditemui, carian harus ditamatkan dan hasilnya harus dipaparkan. Algoritma sedemikian dipanggil linear.
Algoritma linear digunakan untuk mencari elemen maksimum (minimum) tatasusunan. Ini juga merupakan algoritma carian. Tetapi di sini kita terpaksa pergi ke penghujung tatasusunan, kerana adalah perlu untuk membandingkan semua elemen dengan nilai maksimum (minimum) semasa dan jika elemen semasa lebih besar (kurang) daripada nilai maksimum (minimum), gantikan nilai maksimum (minimum).
|
Satu lagi pendekatan untuk menyelesaikan masalah ini adalah mungkin. Anda boleh menggunakan keluar awal dari gelung jika nilai yang diperlukan ditemui.
Dalam C++, pernyataan break digunakan untuk keluar dari gelung;
|
Carian Binari
Carian binari (atau binari) ialah algoritma carian yang cekap dan lebih pantas daripada carian linear. Sebagai contoh, untuk tatasusunan 1024 elemen, carian linear dalam kes terburuk (apabila elemen yang dikehendaki tiada dalam tatasusunan) akan memproses semua 1024 elemen, tetapi ia cukup untuk memproses 10 elemen dengan carian binari. Keputusan ini dicapai kerana fakta bahawa selepas langkah pertama gelung, kawasan carian mengecil kepada 512 elemen, selepas &ndash kedua; sehingga 256 dsb.
Kelemahan algoritma sedemikian ialah keperluan untuk pesanan data, serta keupayaan untuk mengakses mana-mana elemen data dalam masa yang tetap (tidak bergantung pada jumlah data). Oleh itu, algoritma tidak boleh berfungsi pada tatasusunan tidak tertib.
Algoritma
- Pilih elemen tengah
A[c] dan bandingkan dengan X.
- Jika
X = A[c] kemudian dijumpai (berhenti).
- Jika
X < A[c], cari lagi pada separuh masa pertama.
- Jika
X > A[c], lihat lebih jauh ke dalam separuh masa kedua.
Pelaksanaan
L = 0; R=N; // segmen awal
manakala ( L < R - 1)
{
c = (L + R) / 2; // jumpa tengah
jika ( X < A[c] ) // mampatan segmen
R=c;
lain
L = c;
}
jika ( A[L] == X)
cout << "A" << L<< "]=" << x;
lain
cout << "Tidak ditemui";
di mana:
A - tatasusunan sumber,
N - saiz tatasusunan,
X - nombor carian,
Pelaksanaan lain boleh dilakukan.
Contohnya, menggunakan keluar awal dari gelung
L = 0; R = N - 1;
manakala (R >= L)
{
c = (L + R) / 2;
jika ( X == A[c] )
{
nX = c;
pecah;
}
jika (X < A[c]) R = pertengahan - 1;
jika (X > A[c]) L = pertengahan + 1;
}
jika ( nX < 0)
cout << "Tidak ditemui";
lain
cout << "A" << nX<< "]=" << X;
|
Perbandingan algoritma carian linear dan binari mengikut bilangan perbandingan
Contoh
| # |
Carian Baris |
Carian Binari |
| 2 |
2 |
2 |
| 16 |
16 |
5 |
| 1024 |
1024 |
11 |
| 1048576 |
1048576 |
21 |
Kelebihan isihan binari ialah ia lebih pantas.
Keburukan- tatasusunan pra-isih diperlukan.
|