binary search

Cards (5)

  • Binary  Search
    • Satu teknik yang menggunakan proses carian dwipilihan.
    • Item dalam senarai akan diisih dalam urutan menaik.
    • Proses carian akan dimulai dari ditengah-tengah senarai item.
    • Jika carian telah ditemui, maka proses carian akan ditamatkan.
    • Teknik ini akan membandingkan item ditengah-tengah dengan item yang bersebelahan dengannya.
    • Teknik ini lebih efesien kerana tidak perlu menyemak semua senarai dan sesuai untuk item yang banyak.
  • Algoritma bagi binary search adalah seperti berikut:
    1. Pastikan item-item dalam senarai yang diberi telah diisih mengikut urutan menaik
    2. Lihat item yang berada ditengah senarai
    3. Bandingkan item carian dengan item yang berada di tengah senarai
    4. Jika nilai item carlan sama dengan nilai item yang berada di tengah senarai, carian
    5. Jika nilai item carian kurang daripada nilal item yang berada di tengah senaral, abaikan item di tengah senarai dan item-item selepasnya. Kemudian, lihat pada senarai yang tinggal
  • Algoritma bagi binary search adalah seperti berikut:
    6) Jika nilai item carian lebih daripada nilai item di tengah senarai, abaikan item di tengah senarai dan item-item sebelumnya. Kemudian, lihat pada senarai yang tinggal menggunakan teknik menjumpai item carian
    7) Ulang langkah 2 hingga Langkah 6 sehingga item carian dijumpai atau apabila apabila carian selesai tanpa menggunakan teknik menjumpai item carian
  • Pseudokod 
    1. Mula
    2. Setkan senarai L = [P, Q, R, S, T]
    3. Isytihar pemboleh ubah n, i, j, m, b
    4. Setkan n = 5
    5. Setkan i = 0
    6. Setkan j=n-1
    7. Masukkan satu nilai carian b
    8. while i < j
        8.1 Setkan m = (i + j) /2
        8.2 Jika b == Lm
           8.2.1 Papar "item ada dalam senarai"
           8.2.2 Keluar gelung
  • Carta alir