Searching (Sequential and Binary Searching)
Konsep dan Istilah
Internal Search : algoritma pencarian yang dilakukan dalam main memory komputer
External Search : algoritma pencarian yang melibatkan external media menambah main memory
Key : sebuah subset dari isi sebuah data yang digunakan untuk perbandingan selama proses pencarian
Big-O Notation : notasi yang digunakan untuk mengindikasikan kenaikan (Order of growth) unjuk kerja dari sebuah algoritma searching
Sequential Search
Sequential Search adalah teknik pencarian data dimana data dicari secara urut dari depan ke belakang atau dari awal sampai akhir. berdasarkan key yang di cari Kelebihan dari proses pencarian secara sequential ini
- jika data yang dicari terletak didepan, maka data akan ditemukan dengan cepat.
Tetapi dibalik kelebihannya ini, teknik ini juga memiliki kekurangan.
- jika data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan waktu yang lama dalam proses pencariannya.
- beban komputer akan semakin bertambah jika jumlah data dalam array sangat banyak.
Proses:
- Mulai dari awal(atau dari akhir) cek seluruh record dalam array atau list, baca satu persaru
- Temukan record sesuai dengan key yang dicari.
- Proses Searching berhenti karena salah satu alasan.
- Success – Found the target key
- End of List – No more records to compare
Diaplikasikan pada Array (sorted &unsorted) atau Linked List.
Sequential Search Analysis
Bagaimana worst case dan average case untuk metode sequential search?
- Kita harus mendefinisikan O-notation untuk nilai dari operasi yang dibutuhkan dalam pencarian
- Jumlah operasi pencarian bergantung pada nilai n, yaitu jumlah elemen dalam list.
Worst Case Time for Sequential Search:
Untuk sebuah array dengan elemen, makaworst case time untuk sequential search requires n array accesses: O
Kondisi yang mengharuskan pengecekanterhadap semua elemen array (record) adalah:
- Record yang dicari berada pada posisiterakhir dari array.
- Setelah pengecekan seluruh elemen array,ternyata record yang dicari tidak berhasilditemukan dalam array tersebut.
Algoritma Sequential Search
- i ← 0
- ketemu ←false
- Selama (tidak ketemu) dan (i < N) kerjakan baris 4
- Jika (Data[i] = key) maka
- ketemu ←true
- jika tidak
- i ←i+1
- Jika (ketemu) maka
- i adalah indeks dari data yang dicari
- jika tidak
- data tidak ditemukan
implementasi sequential searching on javacode
<br />public class sequential_search {<br /> public static void main(String[]args) throws Exception {<br /> int a[] = new int[4];<br /> int x,i,posisi;<br /> boolean ada;<br /> a[0] = 2;<br /> a[1] = 62;<br /> a[2] = 32;<br /> a[3] = 42;<br /> ada = false;<br /> posisi = 0;<br /> x = 32;<br /><br /> for (i=0; i<=3; i++){<br /> if (a[i] == x) {<br /> ada = true;<br /> if (ada== true){<br /> System.out.print(" ketemu posisi " + (i+1));<br /> }<br /> else{System.out.print(" tidak ada ");<br /> }<br /> }<br /> }<br /> }<br />}<br /><br />
Binary Search
- Define working range as entire list
- Repeat till done
- Select the middle record
- Compare the target key value with the keyof the selected “record”
- Comparison results:
- Key < middle record : Range = First half
- Key > middle record : Range = Last half
- Key = middle record: Success, Done
- Applies only to Sorted Array List
Algoritma Binary Search
- L ← 0
- R ← N–1
- ketemu ←false
- Selama (L <= R) dan (tidak ketemu) kerjakan baris 5sampai dengan 8
- m ← (L+R) /2
- Jika (Data[m] = key) maka ketemu ←true
- Jika (key < Data[m]) maka R ←m–1
- Jika (key > Data[m]) maka L ←m+1
- Jika (ketemu) maka
- m adalah indeks dari data yang dicari
- jika tidak
- data tidak ditemukan
contoh implementasi search
//ListsCompared.java
//compare times to do searches, iterations and random accesses in ArrayList and LinkedList
//generate random ints, add to an arraylist and to a linkedlist,
//do iterations, do random accesses, do random searches,
//then sort and do random binary searches, comparing times.
import java.util.*;
import javax.swing.*;
class ListsCompared {
public static void main(String[] args) {
String input;
int size;
int range;
int randInt;
int numberAccesses, randIndex;
int numberSearches, hits, misses;
long timeStart, timeEnd;
double elapsedSeconds;
ArrayList myArrayList = new ArrayList();
LinkedList myLinkedList = new LinkedList();
input = JOptionPane.showInputDialog( "Enter number of random ints to generate" );
size = Integer.parseInt( input );
input = JOptionPane.showInputDialog( "Enter upper range of the random ints" );
range = Integer.parseInt( input );
for (int i=1; i<=size; i++) {
randInt = (int)(Math.random()*range);
myArrayList.add(new Integer(randInt));
myLinkedList.add(new Integer(randInt));
}
//****************************************************
//** iteration tests
Iterator it = myArrayList.iterator();
timeStart = System.currentTimeMillis();
while (it.hasNext())
it.next(); //don't actually do anything with each item
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("ArrayList iteration ("+size+" items)");
System.out.println(" Elapsed time: " + elapsedSeconds + "s" +
" Time per item: " + (elapsedSeconds/size) + "s");
it = myLinkedList.iterator();
timeStart = System.currentTimeMillis();
while (it.hasNext())
it.next();
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("LinkedList iteration ("+size+" items)");
System.out.println(" Elapsed time: " + elapsedSeconds + "s" +
" Time per item: " + (elapsedSeconds/size) + "s");
System.out.println();
//****************************************************
//** random access tests
input = JOptionPane.showInputDialog( "Enter number of random accesses to do in the list" );
numberAccesses = Integer.parseInt( input );
//*** ArrayList
timeStart = System.currentTimeMillis();
for (int i=1; i<=numberAccesses; i++) {
randIndex = (int)(Math.random()*size); //random index
myArrayList.get(randIndex);
}
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("ArrayList ("+size+" items) random "+numberAccesses+ " gets");
System.out.println(" Elapsed time: " + elapsedSeconds + "s" +
" Time per search: " + (elapsedSeconds/numberAccesses) + "s");
//*** LinkedList
timeStart = System.currentTimeMillis();
for (int i=1; i<=numberAccesses; i++) {
randIndex = (int)(Math.random()*size); //random index
myLinkedList.get(randIndex);
}
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("LinkedList ("+size+" items) random "+numberAccesses+ " gets");
System.out.println(" Elapsed time: " + elapsedSeconds + "s" +
" Time per search: " + (elapsedSeconds/numberAccesses) + "s");
System.out.println();
//****************************************************
//** unsorted sequential search tests
input = JOptionPane.showInputDialog( "Enter number of random sequential searches to do in the unsorted list" );
numberSearches = Integer.parseInt( input );
//***sequential search ArrayList
hits = misses = 0;
timeStart = System.currentTimeMillis();
for (int i=1; i<=numberSearches; i++) {
randInt = (int)(Math.random()*range);
if (myArrayList.contains(new Integer(randInt)))
hits++;
else
misses++;
}
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("ArrayList ("+size+" items) unsorted sequential search: hits: "+hits+" misses: "+misses);
System.out.println(" Elapsed time: " + elapsedSeconds + "s" +
" Time per search: " + (elapsedSeconds/numberSearches) + "s");
//***sequential search LinkedList
hits = misses = 0;
timeStart = System.currentTimeMillis();
for (int i=1; i<=numberSearches; i++) {
randInt = (int)(Math.random()*range);
if (myArrayList.contains(new Integer(randInt)))
hits++;
else
misses++;
}
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("LinkedList ("+size+" items) unsorted sequential search hits: "+hits+" misses: "+misses);
System.out.println(" Elapsed time: " + elapsedSeconds + "s" +
" Time per search: " + (elapsedSeconds/numberSearches) + "s");
System.out.println();
//****************************************************
//** sorted sequential search tests
//sort the data
Collections.sort(myArrayList);
Collections.sort(myLinkedList);
//***sequential search ArrayList
hits = misses = 0;
timeStart = System.currentTimeMillis();
for (int i=1; i<=numberSearches; i++) {
randInt = (int)(Math.random()*range);
if (myArrayList.contains(new Integer(randInt)))
hits++;
else
misses++;
}
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("ArrayList ("+size+" items) sorted sequential search: hits: "+hits+" misses: "+misses);
System.out.println(" Elapsed time: " + elapsedSeconds + "s" +
" Time per search: " + (elapsedSeconds/numberSearches) + "s");
//***sequential search LinkedList
hits = misses = 0;
timeStart = System.currentTimeMillis();
for (int i=1; i<=numberSearches; i++) {
randInt = (int)(Math.random()*range);
if (myArrayList.contains(new Integer(randInt)))
hits++;
else
misses++;
}
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("LinkedList ("+size+" items) sorted sequential search hits: "+hits+" misses: "+misses);
System.out.println(" Elapsed time: " + elapsedSeconds + "s" +
" Time per search: " + (elapsedSeconds/numberSearches) + "s");
System.out.println();
//**************************************************
//** binary search tests
input = JOptionPane.showInputDialog( "Enter number of random binary searches to do in the sorted list" );
numberSearches = Integer.parseInt( input );
//***binary search ArrayList
hits = misses = 0;
timeStart = System.currentTimeMillis();
for (int i=1; i<=numberSearches; i++) {
randInt = (int)(Math.random()*range);
if (Collections.binarySearch(myArrayList,(new Integer(randInt))) >= 0) //***
hits++;
else
misses++;
}
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("ArrayList ("+size+" items) binary search hits: "+hits+" misses: "+misses);
System.out.println(" Elapsed time: " + elapsedSeconds + "s" +
" Time per search: " + (elapsedSeconds/numberSearches) + "s");
//***binary search LinkedList
hits = misses = 0;
timeStart = System.currentTimeMillis();
for (int i=1; i<=numberSearches; i++) {
randInt = (int)(Math.random()*range);
if (Collections.binarySearch(myArrayList,(new Integer(randInt))) >= 0) //***
hits++;
else
misses++;
}
timeEnd = System.currentTimeMillis();
elapsedSeconds = (timeEnd-timeStart)/1000.0;
System.out.println("LinkedList ("+size+" items) binary search hits: "+hits+" misses: "+misses);
System.out.println(" Elapsed time: " + elapsedSeconds + "s" +
" Time per search: " + (elapsedSeconds/numberSearches) + "s");
System.out.println();
}
}
/*
range same as size
For each of ArrayList and LinkedList:
iteration:
#items total time time per item
---------- ---------- -------------
10,000
100,000
1,000,000
random access:
#items #accesses total time time per item
---------- --------- ---------- -------------
10,000 1000
10,000 10000
100,000 10000
100,000 100000
for both unsorted and sorted sequential search
#items #searches total time time per search
---------- --------- ---------- ---------------
10,000 1000
10,000 10000
100,000 1000
binary search
#items #searches total time time per search
---------- --------- ---------- ---------------
10,000 1000
10,000 10000
100,000 10000
100,000 100000
1,000,000 1000000
*/
sumber:
1. http://lecturer.eepis-its.edu/~entin/Struktur%20Data%20%26%20Algoritma/teori/Minggu%2013%20Searching.pdf
2. http://www.davidwills.net/cmis242/ListsCompared.java
Advertisement
Leave a Comment
