Sequential search dan Binary search

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.

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.

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 SEARCH

3.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 Implementation

Buat 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 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;
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));
 }

}