E-Book (How To Solve It By Computer) = Algorithm 5.7 Binary Search.

Asslamu'alaikum w.w.,

Pada Kesempatan ini saya akan memposting tentang : Algorithm Algorithm 5.7 Binary Search. Ini merupakan dari Materi SEARCHING AND SORTING.

Algoritma :

Pencarian pada data yang telah terurut menunjukkan kinerja yang lebih baik daripada pada data yang masih acak, hal ini karena dapat segera diketahui bahwa x tidak terdapat dalam larik bila ditemukan elemen yang lebih besar dari x.

Binary searching atau biasa disebut pencarian bagi dua merupakan metode pencarian yang paling efisien untuk data yang telah terurut. Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat.
Langkah-langkah pencarian bagi dua untuk data yang telah terurut secara ascending:
1. Bagi dua elemen larik yang telah terurut secara ascending, dengan cara menentukan elemen awal pencarian, elemen akhir pencarian dan elemen tengahnya.
    - elemen awal pencarain (lo) = 1
    - elemen akhir pencarain (hi) = n
    - elemen tengah = (lo + hi) div 2

Misalnya terdapat larik L dengan 9 elemen yang telah terurut secara ascending seperti dibawah ini, maka kita akan menentukan elemen awal, akhir dan tengah pencariannya.

    3
    6 7 9 10
    15 20 30 45

    Lo = 1
    Hi = 9
    Mid = ( 1 + 9 ) div 2 = 5
2. Jika elemen yang dicari ada pada elemen di mid, maka ketemu.
3. Jika elemen yang ada di mid > elemen yang dicari, maka hi berubah
    Hi = mid - 1
4. Jika elemen yang ada di mid < elemen yang dicari, maka lo berubah Lo = mid + 1 5. Ulangi langkah-langkah tersebut sampai data yang dicari ditemukan atau sampai elemen telah habis dibagi. Contoh: 3 6 7 9 10 15 20 30 45 Misalnya data yang dicari (x) = 7 1. lo = 1 hi = 9 mid = (1 + 9) div 2 = 5 L[5] = 10 L[mid] > x, maka hi berubah.
      2. hi = mid -1 = 5 – 1 = 4
      lo = 1
      mid = ( 1 + 4 ) div 2 = 2
      L[2] = 6
L[mid] < x, maka lo berubah 3. lo = mid +1 = 2 + 1 = 3 hi = 4 mid = ( 3 + 4 ) div 2 = 3 L[3] = 7 L[mid] = x, maka data ditemukan Pseudocode Pencarian bagi dua: Algoritma bin_searching; Var lo,hi,mid,n,x,idx :integer; ketemu : boolean; L : array [1..100] of integer; Begin {misalnya telah terdapat sekumpulan data yng tersimpan di dalam larik L} lo ß 1; hi ß n; ketemu ß false; while (not ketemu) and (lo <= hi) do midß (lo + hi ) div 2; If L[mid] = x then ketemu ß true Else If ( L[mid] > x ) then
lo ß mid + 1
Else
hi ß mid – 1;
End if
End if
End while
If (ketemu) then
Idx ß mid
Else
Idx ß -1;
End if
End.

Semoga Bermanfaat.

Wassalamu'alaikum w.w.