pencarian sekuensial
Dalam ilmu komputer, pencarian linear adalah sebuah algoritma pencarian, juga dikenal sebagai pencarian sekuensial, yang cocok untuk mencari sebuah nilai tertentu pada sebuah himpunan data.
Algoritma ini beroperasi dengan memeriksa setiap elemen dari sebuah list sampai sebuah kecocokan ditemukan. Pencarian linear bekerja dalam O(n). Jika data terdistribusi secara acak, rata-rata ada n/2 pembandingan akan dilakukan. Kasus terbaik adalah ketika nilai yang dicari adalah elemen pertama dari list, kasus ini hanya memerlukan 1 pembandingan. Kasus terburuk adalah ketika nilai yang dicari tidak ada dalam list, yang memerlukan n pembadingan.
Modul List pada pustaka standard OCaml mendefinisikan sebuah fungsi "mem" yang mengembalikan nilai true jika elemen yang diberikan berada dalam list atau false jika tidak. Fungsi ini dinyatakan sebagai berikut:
let rec mem x = function [] -> false | h :: t -> h=x || mem x t
Pencarian linear dapat diimplementasikan secara matematika dengan pencocokan pola :
Mem[x_, {___, x_, ___}] := True Mem[_, _] := False
Pencarian linear dapat digunakan untuk mencari sebuah list tak berurut. Pencarian biner adalah pencarian yang lebih efisien yang dapat digunakan untuk mencari sebuah list berurut.
Jika diperlukan beberapa kali pencarian, disarankan untuk menggunakan struktur data yang lebih efisien. Satu pendekatan adalah dengan mengurutkan terlebih dahulu kemudian gunakan pencarian biner untuk setiap pencarian. Cara lain yang lazim adalah membuat sebuah tabel hash dan dilakukan pencariaan hash.
Algoritma pencarian biner
Umumnya, untuk mencari sebuah nilai dalam array disortir, kita harus melihat melalui elemen-elemen dari array satu per satu, sampai mencari nilai ditemukan. Dalam kasus dari pencarian nilai absen dari array, kita melewati semua elemen. Rata-rata, kompleksitas algoritma tersebut adalah proporsional dengan panjang array.
Situasi perubahan signifikan, ketika array diurutkan. Jika kita tahu itu, kemampuan akses acak dapat dimanfaatkan sangatefisien untuk menemukan pencarian nilai cepat. Biaya algoritma pencarian mengurangi untuk logaritma biner dari panjang array. Untuk referensi, log 2 (1 000 000) ≈ 20. Ini berarti, bahwa dalam kasus terburuk, algoritma membuat 20 langkah untuk menemukan nilai dalam array diurutkan dari satu juta elemen atau mengatakan, bahwa ia tidak hadir itu array.
Algoritma
Algoritma cukup sederhana. Hal ini dapat dilakukan secara rekursif salah satu atau iteratif:
- mendapatkan elemen tengah;
- jika elemen tengah sama dengan nilai yang dicari, algoritma akan berhenti;
- sebaliknya, dua kasus yang mungkin:
- mencari nilai kurang, dari elemen tengah. Dalam hal ini, pergi ke langkah 1 untuk bagian array, sebelum elemen tengah.
- mencari nilai lebih besar, daripada elemen tengah. Dalam hal ini, pergi ke langkah 1 untuk bagian array, setelah elemen tengah.
Sekarang kita harus mendefinisikan, kapan iterasi harus berhenti. Kasus pertama adalah ketika dicari unsur ditemukan.Kedua satu adalah ketika subarray tidak memiliki elemen. Dalam hal ini, kita dapat menyimpulkan, bahwa mencari nilai tidak hadir dalam array.
Contoh
Contoh 1. Temukan 6 di {-1, 5, 6, 18, 19 25,, 46, 78, 102, 114}.
Langkah 1 (elemen tengah adalah 19> 6):
-1 5 6 18 19 25 46 78 102 114
-1 5 6 18 19 25 46 78 102 114
Langkah 2 (elemen tengah adalah 5 <6):
-1 5 6 18 19 25 46 78 102 114
-1 5 6 18 19 25 46 78 102 114
Langkah 3 (elemen tengah adalah 6 == 6):
-1 5 6 18 19 25 46 78 102 114
-1 5 6 18 19 25 46 78 102 114
Contoh 2. Cari 103 di {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.
Langkah 1 (elemen tengah adalah 19 <103):
-1 5 6 18 19 25 46 78 102 114
-1 5 6 18 19 25 46 78 102 114
Langkah 2 (elemen tengah adalah 78 <103):
-1 5 6 18 19 25 46 78 102 114
-1 5 6 18 19 25 46 78 102 114
Langkah 3 (elemen tengah adalah 102 <103):
-1 5 6 18 19 25 46 78 102 114
-1 5 6 18 19 25 46 78 102 114
Langkah 4 (elemen tengah adalah 114> 103):
-1 5 6 18 19 25 46 78 102 114
-1 5 6 18 19 25 46 78 102 114
Langkah 5 (dicari nilai tidak hadir):
-1 5 6 18 19 25 46 78 102 114
-1 5 6 18 19 25 46 78 102 114
Analisis Kompleksitas
keuntungan besar dari algoritma ini adalah yang kompleksitas itu tergantung pada ukuran array logaritmis dalam kasus terburuk. Dalam prakteknya ini berarti, algoritma yang akan melakukan paling banyak log 2 (n) iterasi, yang merupakan angka yang sangat kecil bahkan untuk array besar. Hal ini dapat terbukti sangat mudah. Memang, pada setiap langkah ukuran dicari bagian berkurang setengahnya. Algoritma berhenti, jika tidak ada unsur untuk mencari masuk Oleh karena itu, pemecahan ketimpangan berikut dalam bilangan bulat:
n / 2 iterasi> 0
mengakibatkan
Iterasi <= log 2 (n).
Ini berarti, bahwa kompleksitas algoritma pencarian biner waktu adalah O (log 2 (n)).
Kode snippet.
Anda dapat melihat solusi rekursif untuk Java dan berulang untuk C + + di bawah ini.
Jawa
/ **
* pencarian untuk sebuah nilai di diurutkan susunan
*
* @ Param susunan
* susunan untuk pencarian di
* @ Param nilai
* pencarian nilai
* @ Param kiri
* indeks dari kiri batas
* @ Param kanan
* indeks dari kanan batas
* @ Kembali posisi dari pencarian nilai, jika itu menyajikan di yang susunan atau - 1, jika
* itu adalah absen
* /
binarySearch int (int [] array, nilai int, int kiri, kanan int) {
if (kanan> kiri)
return -1;
int tengah = (kiri + kanan) / 2;
if (array [tengah] == nilai)
kembali menengah;
lain if (array [tengah] nilai>)
kembali binarySearch (array, nilai, kiri, tengah - 1);
lain
kembali binarySearch (array, nilai, tengah + 1, kanan);
}
C + +
/ *
* Mencari nilai dalam array diurutkan
* Arr adalah array untuk mencari di
* Nilai dicari nilai
* Kiri adalah indeks dari batas kiri
* Benar adalah suatu indeks batas kanan
* Kembali posisi pencarian nilai, jika menyajikan dalam array
* Atau -1, jika tidak hadir
* /
int binarySearch (int arr [], nilai int, int kiri, kanan int) {
while (<kiri = kanan) {
int tengah = (kiri + kanan) / 2;
if (arr [tengah] == nilai)
kembali menengah;
else if (arr [tengah]> nilai)
kanan = tengah - 1;
lain
kiri = tengah + 1;
}
return -1;
Tidak ada komentar:
Posting Komentar