[Powered by Google Translate] [Pencarian Linear] [Patrick Schmid, Universitas Harvard] [This Is CS50.] [CS50.TV] Searching adalah sesuatu yang mungkin Anda lakukan lebih sering dari yang Anda pikirkan. Jelas, setiap kali Anda membuka browser web dan mencari halaman web - atau mencari teman di situs jejaring sosial favorit Anda - Anda cari. Tapi itu hanya sebagian kecil dari pencarian yang Anda lakukan setiap hari. Bila Anda ingin menemukan bahwa satu kemeja biru di lemari, atau blus merah sempurna untuk kesempatan, Anda cari. Ketika Anda pergi ke toko yang Anda belum pernah ke sebelumnya, dan Anda sedang mencari brokoli di lorong menghasilkan Anda cari. Apa yang Anda mungkin sudah mulai memperhatikan adalah bahwa tergantung pada apa yang Anda cari atau bagaimana item yang terorganisir ketika Anda sedang mencari mereka memiliki efek pada bagaimana Anda mencari. Misalnya, jika kemeja Anda tergantung di lemari, Anda mungkin bisa saja memilih keluar tanpa banyak mencari. Jika Anda menganggap Anda harus berjalan menyusuri lorong untuk mendapatkan brokoli, Anda mungkin harus melihat semua sayuran lainnya sebelum Anda menemukan bahwa brokoli. Pencarian linear adalah contoh dari salah satu metode pencarian tersebut - atau algoritma. Seperti namanya, Metode ini mencari untuk item secara linear, satu demi satu. Jadi, ketika Anda melihat hasil dari mesin pencari favorit Anda dan Anda membaca daftar hasil, Anda menggunakan pencarian linear. Oke. Mari kita lihat contoh. Katakanlah kita memiliki daftar nomor - 2, 4, 0, 5, 3, 7, 8, dan 1 - dan kami sedang mencari angka 0. Jelas, Anda hanya dapat melihat bahwa 0 berada di posisi ketiga. Tapi, sebuah program komputer yang tidak beruntung. Hal ini hanya bisa "melihat" nomor satu pada suatu waktu. Jadi, mulai pada awal daftar, hanya "melihat" 2. Program ini kemudian memeriksa - 2 adalah sama dengan 0? Jelas tidak. Jadi melanjutkan ke nomor berikutnya, 4. Apakah 4 0 yang sama? Nope. Selanjutnya satu, 0. Ah! Zero adalah sama dengan 0. Ada yang kita miliki! Itu di posisi ketiga. Oke. Mari kita lihat beberapa pseudocode. Ini hanya beberapa baris panjang, tapi mari kita lihat salah satu baris pada satu waktu. Pertama, mari kita mendefinisikan fungsi - dan kita akan menyebutnya pencarian linear - dan dibutuhkan dua argumen - key dan array. Kuncinya adalah nilai yang kita cari, sehingga pada contoh sebelumnya, itu nol. Array adalah daftar nomor yang memiliki semua nilai-nilai yang kita akan mencari. Jadi, apa yang ingin kita lakukan adalah kita ingin melihat - dari semua posisi, sehingga mulai dari awal dari array til akhir dari array - jadi panjang array - melihat setiap posisi tunggal dan memeriksa masing-masing. Jadi itulah apa yang "untuk" loop lakukan. Dan pada posisi masing-masing, kita akan katakan "Apakah itu nilai pada posisi saat ini sama dengan kunci yang kita cari?" Jadi - dalam contoh sebelumnya lagi, kuncinya adalah 0 - jadi kita katakan "Apakah array pada posisi saya sama dengan nol?" Jika ya, kita akan kembali 'i' karena itulah posisi saat ini kita berada di. Jadi, dalam contoh sebelumnya, itu posisi ketiga. Jika kita sudah melalui seluruh array dan kami tidak menemukan apa pun - jadi katakanlah kita sedang mencari nomor 500 yang jelas tidak dalam contoh itu - kita harus kembali sesuatu, dan kita akan kembali -1. Dan kami hanya mengembalikan -1 karena itulah posisi yang tidak ada dalam array. Dan sehingga berarti ketika Anda mendapatkannya kembali dari fungsi ia mengatakan "Hmm, oke. Kurasa aku tidak menemukan apa-apa. Sehingga 500 tidak pernah ada di sana. " Yang menyenangkan tentang pencarian linear adalah bahwa itu akan bekerja pada setiap daftar item, terlepas dari bagaimana item yang diperintahkan. Tidak peduli di mana brokoli dalam lorong memproduksi. Selama Anda berjalan menyusuri lorong dari awal sampai akhir, Anda pasti menemukannya, dengan asumsi toko belum kehabisan brokoli, tentu saja. Tapi kekuatan itu terbesar adalah juga kelemahan itu terbesar. Katakanlah Anda memiliki daftar nomor dua ratus yang diurutkan dari 1 sampai 200. Jika Anda sedang mencari nomor 198, Anda harus mencari hampir seluruh daftar nomor sebelum Anda menemukan yang Anda cari. Harus ada cara yang lebih baik! Yakinlah ada. Tapi, itu topik untuk video lain. Juga, jangan khawatir! Hanya karena pencarian linear bukanlah solusi terbaik dalam segala situasi, itu tidak berarti bahwa itu tidak berguna. Jika tidak, bagaimana Anda akan menemukan bahwa brokoli di lorong menghasilkan? Nama saya adalah Patrick Schmid, dan ini adalah CS50. [CS50.TV]