tajuk 2 jenis-jenis carian

MTE 3104 MATEMATIK KEPUTUSAN

TAJUK 2 JENIS-JENIS CARIAN

2.1 SINOPSIS

Carian adalah proses menentukan sama ada sesuatu nilai diberi wujud

atau tidak dalam struktur data. Ia adalah proses mencari elemen tertentu

dalam susunan barisan yang teratur, misalnya, mencari sama ada skor

yang tertentu dimasukkan ke dalam senarai skor. Carian adalah satu

tugas yang biasa dalam pengaturcaraan komputer. Terdapat banyak

algoritma dan struktur data yang dikhaskan untuk carian.

Dalam topik ini, kita akan meneroka proses carian linear atau berurutan

dan kemudian membandingkan dengan proses carian binari.

2.2 HASIL PEMBELAJARAN

1.Huraikan proses carian linear(linear search algorithm) atau berurutan

(indexed sequential search algorithm).

2. Menerangkan proses carian binari (binary search algorithm)

6


2.3 KERANGKA TAJUK

2.4 Algoritma Carian Linear

Algoritma carian linear adalah algoritma yang paling ringkas.

Carian linear membandingkan unsur utama (key), dengan setiap unsur

dalam senarai. Ini berterusan sehingga kekunci dengan satu elemen

dalam senarai atau senarai habis tanpa perlawanan apa-apa yang

dijumpai.

Carian Linear tidak cukup berkesan. Sasaran yang kita cari boleh

diletakkan pada akhir susunan, yang memerlukan kita mencari setiap

elemen tunggal dalamsusunan. Sebagai contoh, kita perlu mencari

1000 elemen jika kita mempunyai susunan 1000 elemen. Sasaran juga

mungkin berada di suatu tempat di tengah-tengah susunan,

menghendaki kita mencari separuh daripada semua elemen dalam

susunan. Kita perlu mencari kira-kira 500 elemen dalam susunan 1000

elemen tersebut.

Pada umumnya, semak setiap item data seterusnya untuk melihat jika

ia memenuhi kriteria.Tiada sekatan ke atas data. Carian dilaksanakan

walaupun data tidak disusun secara urutan tetapi carian ini adalah yang

paling tidak cekap.Jika item tidak diperolehi, periksa setiap item data

seterusnya.Teruskan mencari secara linear sehingga nilai dikehendaki

diperolehi.

7

JENIS-JENIS CARIAN

Algoritma carian linear

Algoritma carian indeks berurutan (indexed sequential search algorithm)

Algorithma carian binari


Contoh-contoh algoritma carian linear:

i) Bagaimana untuk mencari nama seseorang?

-berikan nombor telefon mereka

-cari dari buku panduan telefon

-berikan nombor I.C mereka

ii) Mencari sebuah buku dari susunan buku-buku.

iii) Mencari barang yang hilang.

iv) Mencari alamat sesuatu tempat.

Contoh penggunaan Algoritma Carian Linear.

10 7 1 3 -4 2 20

Rajah 2.1 Mencari nombor dari susunan elemen.

Cari nombor 3 dari susunan di atas menggunakan carian linear.

Mula pada elemen pertama dalam susunan. Adakah nilai pertama 3?

10 7 1 3 -4 2 20

Rajah 2.2 Adakah nombor pertama nombor 3?

Tidak, Adakah ia berada pada elemen seterusnya?

8


10 7 1 3 -4 2 20

Rajah 2.3 Adakah elemen kedua nombor 3 ?

Tidak sama sekali. Mari lihat elemen seterusnya.

10 7 1 3 -4 2 20

Rajah 2.4 Adakah elemem ketiga nombor 3?

Tidak, lakukan carian untuk elemen seterusnya.

10 7 1 3 -4 2 20

Rajah 2.4 Adakah elemen keempat nombor 3?

Ya.anda telah menemuinya!! Anda telah menemui nombor 3 selepas 4

perbandingan. Sekarang anda telah memahami idea menggunakan carian

linear. Kesimpulannya, anda perlu melalui setiap unsur mengikut urutan,

sehingga anda dapati nilai yang betul.

9


Aktiviti:

Aktiviti 1

Bekerja secara berpasangan, beritahu pasangan anda fikirkan suatu

nombor antara 1 dan 99 (termasuk kedua-duanya). Kemudian dengan

bertanya soalan yang sesuai di mana jawapannya mesti sama ada ya

atau tidak, cuba cari nombor yang difikirkan oleh pasangan anda.

Tujuannya adalah untuk mencari nombor dengan bertanya beberapa

soalan yang mungkin. Tukar giliran dan biarkan pasangan anda cuba

untuk mencari nombor yang anda fikirkan. Ulangi latihan ini beberapa kali

dengan strategi yang berbeza. Bincangkan strategi anda. Berapakah

bilangan soalan minimum, bilangan soalan maksimum dan purata soalan

yang diperlukan?

Aktiviti 2

Gunakan kamus atau direktori telefon untuk menyiasat berapa banyak

item data yang anda perlu lihat apabila mencari perkataan tertentu atau

nombor telefon seseorang. Bandingkan pelbagai strategi dan cuba

gambarkan strategi tersebut secara algoritma.

2.5 Algoritma Carian Indeks Berurutan (Indexed Sequential Search

Algorithm)

Jika data disusun, terdapat dua algoritma boleh digunakan:

i) Algoritma carian indeks berurutan

- Disusun ke dalam fail dan ikuti urutan

ii) Algoritma carian binari

- Keputusan dengan dua pilihan

10


Dalam carian indeks berurutan, data disusun dahulu kemudian

dipecahkan kepada bahagian-bahagian.

Suatu senarai tambahan atau indeks kemudiannya diwujudkan yang

mengandungi item yang pertama atau terakhir dalam setiap pecahan

bahagian.

Contoh penggunaan carian indeks berurutan:

Digunakan di dalam kamus.

Indeks diletakkan pada sudut atas sebelah kanan halaman kamus.

Untuk mencari perkataan yang diberi, anda buka helaian halaman yang

mengandungi indeks perkataan yang dikehendaki. Kemudian lakukan

carian linear pada halaman yang dipilih.

Contoh-contoh lain penggunaan carian indeks berurutan(indexed

sequential algirithm):

i) Satu set data yang terdapat pada sistem komputer - mewujudkan

satu senarai kecil.

ii) Untuk mencari nama bandar di UK dalam senarai kod kawasan

telefon.

- Senarai sub-kod kawasan telefon mengandungi kedudukan

bandar pertama yang namanya bermula dengan A, B, C, ... ..

dan sebagainya.

- Kemudian, untuk mencari York, carian akan dilakukan bermula

dari senarai sub untuk mencari Y.

- Ini akan memberi kedudukan bagi memulakan carian linear bagi

data utama.

11


2.6 Carian Binari

Carian binari adalah pilihan yang lebih cekap untuk mencari tatasusunan. Carian

binari digunakan biasanya dalam bidang sains komputer di mana terdapat satu

konsep yang berkaitan dipanggil Pokok Carian Binari.

Dalam bidang sains komputer, carian binari adalah algoritma carian untuk

mencari satu set data yang disusun untuk suatu nilai tertentu. Carian binari

memerlukan capaian rawak untuk data yang dicari. Dalam bentuk yang paling

mudah, carian binari adalah dengan menganggap data disusun (biasanya oleh

algoritma isihan) dan mengambil kelebihan daripada ciri-ciri itu.

Carian binari adalah suatu algoritma yang memulakan carian di tengah-tengah

susunan. Jika nilai yang dikehendaki lebih kecil daripada nilai di tengah-tengah

susunan, maka separuh susunan kedua diabaikan. Strategi ini kemudian

digunakan untuk separuh pertama susunan. Jika nilainya lebih besar daripada

nilai di tengah-tengah susunan, maka separuh pertama susunan diabaikan.

Strategi ini kemudiannya digunakan untuk separuh kedua susunan. Jika nilainya

berada di tengah-tengah susunan, maka ia telah dijumpai.

Catatan : i) Jika bilangan data adalah ganjil, nilai ditengah dikira menggunakan

m=¿¿

iaitu jika n1 = 12 dan n2 = 20, maka nilai di tengah adalah 16.

ii) Jika bilangan data adalah genap, nilai ditengah dikira daripada nilai

integer yang lebih besar, iaitu jika kedudukan antara 15 dan 24,

maka nilai di tengah adalah 19.5. Dibundarkan kepada 20. Jadi

nilai di tengah adalah 20.

12


Sebagai contoh, jika anda mempunyai 1024 elemen dalam susunan barisan,

dalam keadaan yang paling teruk, carian binari hanya memerlukan 10

perbandingan manakala carian linear memerlukan 1024 perbandingan. Jika anda

mempunyai 1 bilion elemen, carian binari hanya memerlukan 30 perbandingan

manakala carian linear memerlukan 1 bilion perbandingan.

Contoh penggunaan algoritma carian binari.

Mencari nombor 7 dari suatu susunan.

10 7 1 3 -4 2 20

Rajah 2.6: Susunan yang hendak dicari

Cari nombor 7 dari susunan. Mulakan dengan menyusun nombor secara

menaik.

-4 1 2 3 7 10 20

Rajah 2.7: Nombor yang telah disusun secara menaik

Sekarang, lihat susunan di tengah. Ia adalah 3. Nombor ini lebih kecil dari daripada nombor yang dicari. Oleh itu, abaikan separuh yang pertama.

-4 1 2 3 7 10 20

Rajah 2.8: Susunan nombor yang pertama diabaikan.

Lihat pula susunan di tengah daripada baki separuh daripada susunan. Nilai di tengah adalah 10.Nombor ini lebih besar daripada nombor yang dicari, maka abaikan separuh susunan nombor yang kedua.

13


-4 1 2 3 7 10 20

Rajah 2.9: Nombor separuh kedua diabaikan

Lihat baki susunan nombor.Ya. Anda telah menjumpai nombor 7!!

-4 1 2 3 7 10 20

Rajah : Adakah niali keempat no 3?

Anda menjumpai nombor 7 selepas 3 perbandingan. Ini adalah bagaimana

carian binari dilakukan. Ia adalah jelas bahawa algoritma carian binari adalah

lebih cepat daripada algoritma carian linear.

Buku rujukan

Parramore, K., et. al. (2004). Decision Mathematics 1. 3rd ed. U.K. Hodder

Murray.

Parramore, K., et. al. (2004). Decision Mathematics 2 and C . 3rd ed. U.K.

Hodder Murray.

Brian, J, (2005). Decision Mathematics , U.K. Oxford University Press.

14

tajuk 2 jenis-jenis carian

Documents