1.SEARCHING IN COLLECTIONS
Artikel berikut ini akan membahas penerapan algoritma pencarian yang berbeda di Jawa untuk menemukan elemen dalam koleksi.
Pencarian dalam koleksi ini dilakukan untuk menjawab pertanyaan:
*Apakah unsur yang ada dalam koleksi
* Dapatkan elemen dari koleksi
*Menghapus elemen dari koleksi
Koleksi dalam artikel ini digunakan dalam arti luas dan bukan dalam arti Jawa ketat. Untuk pengumpulan contoh kita melihat array saya akan atau daftar.
Pencarian dalam koleksi ini dilakukan untuk menjawab pertanyaan:
*Apakah unsur yang ada dalam koleksi
* Dapatkan elemen dari koleksi
*Menghapus elemen dari koleksi
Koleksi dalam artikel ini digunakan dalam arti luas dan bukan dalam arti Jawa ketat. Untuk pengumpulan contoh kita melihat array saya akan atau daftar.
2. SEQUENTIAL SEARCH
2.1 Overvieew
Sequential search adalah pendekatan sederhana. Mengingat koleksi Anda mencoba setiap elemen dalam koleksi sampai Anda telah menemukan elemen atau sampai Anda mencapai akhir koleksi.
2.2 Implementation
Sequential Search adalah sangat mudah untuk diimplementasikan.
Buat proyek Java "de.vogella.algorithms.search.sequential" dan sebuah paket dengan nama yang sama.
Buat program berikut.
Buat proyek Java "de.vogella.algorithms.search.sequential" dan sebuah paket dengan nama yang sama.
Buat program berikut.
package de.vogella.algorithms.search.sequential;
public class SequentialSearch {
public static boolean contains(int[] a, int b){
for (int i : a) {
if (i==b){
return true;
}
}
return false;
}
}2.3 Test
Anda dapat menggunakan uji JUnit berikut untuk memvalidasi metode semacam Anda. Untuk mempelajari tentang JUnit silakan lihat Tutorial JUnit.package de.vogella.algorithms.search.sequential;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import org.junit.Test;
public class SequentialSearchTest {
@Test
public void testContains() {
int[]a = {1, 2, 3, 4, 5, 19, 17, 7};
assertTrue(SequentialSearch.contains(a, 17));
assertTrue(SequentialSearch.contains(a, 1));
assertTrue(SequentialSearch.contains(a, 2));
assertTrue(SequentialSearch.contains(a, 3));
assertTrue(SequentialSearch.contains(a, 4));
assertFalse(SequentialSearch.contains(a, 10));
}
} 3. BINARY SEARCH3.1 Overview Pencarian biner mensyaratkan bahwa koleksi sudah disortir.Misalnya dengan Quicksort atau mergesort.
Pencarian biner cek elemen di tengah koleksi. Jika elemen pencarian yang lebih kecil atau lebih
besar maka elemen ditemukan maka sub-array didefinisikan yang kemudian mencari lagi. Jika mencari elemen lebih kecil maka elemen ditemukan maka sub-array dari awal array sampai elemen ditemukan.Jika mencari elemen lebih besar maka elemen ditemukan maka sub-array dari elemen
yang ditemukan sampai akhir array.Setelah dicari elemen ditemukan atau koleksi kosong maka pencarian selesai
3.2 ImplementationBuat proyek Java "de.vogella.algorithms.search.binary" dan sebuah paket dengan nama yang sama.
Buat program berikut.package de.vogella.algorithms.search.binary;
public class BinarySearch {
public static boolean contains(int[] a, int b) {
if (a.length == 0) {
return false;
}
int low = 0;
int high = a.length-1;
while(low <= high ) {
int middle = (low+high) /2;
if (b> a[middle] ){
low = middle +1;
} else if (b< a[middle]){
high = middle -1;
} else { // The element has been found
return true;
}
}
return false;
}
}3.3 TestAnda dapat menggunakan uji JUnit berikut untuk memvalidasi metode semacam Anda. Untuk
mempelajari tentang JUnit silakan lihat Tutorial JUnit.package de.vogella.algorithms.search.sequential; package de.vogella.algorithms.search.binary; import org.junit.Test; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; public class BinarySearchTest { @Test public void testContains() { int[]a = {1, 2, 3, 4, 5, 7, 17, 19 }; // assertTrue(BinarySearch.contains(a, 17)); assertTrue(BinarySearch.contains(a, 1)); assertTrue(BinarySearch.contains(a, 2)); assertTrue(BinarySearch.contains(a, 3)); assertTrue(BinarySearch.contains(a, 4)); assertFalse(BinarySearch.contains(a, 10)); } }
