Tip:
Highlight text to annotate it
X
[Powered by Google Translate] [Carian Linear]
[Patrick Schmid, Universiti Harvard]
[Ini Apakah CS50.] [CS50.TV]
Searching adalah sesuatu yang anda mungkin melakukan lebih kerap daripada yang anda fikirkan.
Jelas sekali, setiap kali anda membuka pelayar web
dan mencari laman web -
atau mencari rakan-rakan anda di laman rangkaian sosial kegemaran anda -
anda sedang mencari.
Tetapi itu hanya sebahagian kecil daripada mencari yang anda lakukan pada setiap hari.
Apabila anda ingin mencari bahawa salah satu kemeja biru di dalam almari,
atau blaus merah yang sempurna untuk majlis itu,
anda mencari.
Apabila anda pergi ke kedai yang anda tidak pernah ke sebelum,
dan anda sedang mencari untuk brokoli di lorong hasil
anda mencari.
Apa yang anda mungkin telah mula notis
adalah bahawa bergantung kepada apa yang anda sedang mencari
atau bagaimana perkara-perkara yang dianjurkan apabila anda sedang mencari untuk mereka
ia mempunyai kesan ke atas bagaimana anda mencari.
Sebagai contoh, jika baju anda tergantung di dalam almari,
anda mungkin hanya boleh mengambilnya keluar tanpa banyak mencari.
Jika anda menganggap anda perlu berjalan di lorong
untuk mendapatkan brokoli, anda mungkin perlu untuk melihat semua sayur-sayuran lain
sebelum anda mendapati bahawa brokoli.
Search linear adalah contoh satu mencari kaedah itu - atau algoritma.
Seperti namanya,
kaedah ini mencari item dalam fesyen linear, satu demi satu.
Jadi, apabila anda sedang melihat keputusan dari enjin carian kegemaran anda
dan anda membaca senarai keputusan,
anda menggunakan carian linear.
Okay. Mari kita lihat pada contoh.
Katakanlah kita mempunyai senarai nombor 2, 4, 0, 5, 3, 7, 8, dan 1 -
dan kita sedang mencari untuk 0 bilangan.
Jelas sekali, anda hanya boleh melihat bahawa 0 adalah di kedudukan ketiga.
Tetapi, program komputer tidak begitu bernasib baik.
Ia hanya boleh "melihat" nombor satu pada satu-satu masa.
Jadi, bermula pada awal senarai,
ia hanya "melihat" 2.
Program ini kemudian memeriksa - 2 sama dengan 0?
Sudah tentu tidak. Jadi ia pergi ke nombor yang berikutnya, 4.
Adakah 4 0 yang sama? Nope.
Satu depan, 0. Ah! Sifar adalah sama dengan 0.
Terdapat kita mempunyai! Ia adalah pada kedudukan ketiga.
Okay. Mari kita melihat beberapa pseudokod.
Ia hanya beberapa barisan panjang, tetapi mari kita melihat ia satu baris pada satu masa.
Pertama, mari kita mentakrifkan fungsi - dan kita akan memanggilnya carian linear -
dan ia mengambil masa dua hujah - kunci dan pelbagai.
Utama adalah nilai yang yang kita cari,
jadi dalam contoh sebelum ini, itu adalah sifar.
Pelbagai adalah satu senarai nombor
yang mempunyai semua nilai-nilai yang kita pergi untuk mencari.
Jadi, apa yang kita mahu lakukan ialah kita mahu melihat -
daripada semua jawatan, jadi bermula pada awal sangat array
til akhir sangat array - jadi panjang array -
melihat kedudukan setiap satu dan memeriksa setiap satu.
Supaya apa yang "untuk" gelung lakukan.
Dan pada kedudukan masing-masing, kita akan mengatakan
"Adakah bahawa nilai pada kedudukan yang sama dengan kunci yang kita cari semasa?"
Jadi dalam contoh sebelumnya lagi, utama ialah 0 -
jadi kita mengatakan "Apakah pelbagai pada kedudukan i sama dengan sifar?"
Jika ia, kita akan kembali 'i' kerana itulah kedudukan semasa kita berada di.
Jadi, dalam contoh sebelum ini,
yang kedudukan ketiga.
Jika kita telah melalui pelbagai keseluruhan
dan kita telah tidak dijumpai apa-apa -
jadi mari kita mengatakan kita telah mencari bilangan 500
yang jelas tidak berada dalam contoh bahawa -
kita perlu kembali sesuatu,
dan kita akan kembali -1.
Dan kami hanya kembali -1 kerana itulah kedudukan
yang tidak wujud dalam pelbagai.
Dan supaya bermakna apabila anda mendapatkan ia kembali dari fungsi
ia berkata, "Hmm, okay saya rasa saya tidak menjumpai apa-apa.
Supaya 500 tidak pernah berada di sana. "
Perkara yang baik tentang carian linear adalah bahawa
ia akan bekerja di mana-mana senarai barangan,
tanpa mengira bagaimana barang dipesan.
Ia tidak kira di mana brokoli adalah di lorong hasil.
Sebagai selagi anda berjalan di lorong dari awal hingga akhir,
anda terikat untuk mencari ia,
menganggap kedai tidak kehabisan brokoli, sudah tentu.
Tetapi kekuatan terbesar adalah juga kelemahan terbesar.
Katakanlah anda mempunyai senarai 200 nombor
yang disusun 1-200.
Jika anda sedang mencari untuk beberapa 198,
anda perlu mencari hampir keseluruhan senarai nombor
sebelum anda mencari satu yang anda sedang mencari.
Mesti ada cara yang lebih baik!
Yakinlah ada.
Tetapi, itulah satu topik untuk video lain.
Juga, jangan risau!
Hanya kerana carian linear tidak adalah penyelesaian terbaik dalam semua keadaan,
ia tidak bermakna bahawa ia tidak datang dalam berguna.
Jika tidak, bagaimana anda akan mendapati bahawa brokoli di lorong hasil?
Nama saya adalah Patrick Schmid, dan ini adalah CS50.
[CS50.TV]