[MUSIC PLAYING] Doug LLOYD: Linear pencarian adalah kita algoritma dapat digunakan untuk menemukan elemen dalam array. Sebuah recall algoritma adalah langkah-demi-langkah set instruksi untuk menyelesaikan tugas. 

Pencarian linear Algoritma bekerja sebagai berikut. Iterate melintasi array dari kiri ke tepat, mencari elemen tertentu. 

Dalam pseudocode, yang merupakan lebih versi suling dari kalimat ini, jika elemen pertama adalah apa Anda sedang mencari, Anda dapat berhenti. Jika tidak, pindah ke elemen berikutnya dan terus berulang-ulang sampai Anda menemukan elemen, atau Anda tidak. Jadi kita bisa menggunakan linear algoritma pencarian, misalnya, untuk menemukan nilai target sembilan array ini. Nah kita mulai dari awal. Jika itu yang kami mencari, kita dapat berhenti. Ini tidak, kita tidak mencari 11. Jadi jika tidak, pindah ke elemen berikutnya. 

Jadi kita melihat 23. Apakah 23 apa yang kita cari? Yah tidak, jadi kami pindah ke berikutnya elemen, dan elemen berikutnya, dan kami tetap akan melalui Proses ini berulang dan lebih, sampai kami mendarat pada situasi seperti ini. 

Sembilan adalah apa yang kita cari, dan elemen ini array adalah, itu nilai sembilan. Dan kami menemukan apa yang kita mencari, dan kita bisa berhenti. Pencarian linear memiliki selesai, berhasil. 

Tapi bagaimana kalau kita mencari unsur yang tidak di array kita. Apakah pencarian linear masih bekerja? Nah yakin. Jadi kita ulangi proses ini mulai dari elemen pertama. Jika itu yang kami mencari, kita dapat berhenti. Ini bukan. Jika tidak, kita pindah ke elemen berikutnya. 

Tapi kita bisa terus mengulangi proses ini, memeriksa setiap elemen pada gilirannya, berharap bahwa kita menemukan nomor 50. Tapi kita tidak akan tahu apakah kami telah menemukan jumlah 50 atau jika kita tidak, sampai kita sudah melangkah atas setiap elemen tunggal dari array. 

Hanya sekali kami telah melakukan itu dan tekor, dapat kita simpulkan bahwa 50 tidak dalam array. Dan sehingga pencarian linear algoritma, baik itu gagal, per se. Tapi tidak dalam arti bahwa hal itu tidak berhasil dalam melakukan apa kami meminta untuk dilakukan. 

Itu berhasil sebagai sebanyak itu tidak menemukan 50, tapi 50 tidak dalam array. Tapi kami telah mendalam mencari melalui setiap elemen tunggal dan sebagainya, sementara kita tidak menemukan apa-apa, pencarian linear masih berhasil bahkan jika unsur tidak dalam array. 

Jadi apa kasus terburuk Skenario dengan pencarian linear? Baik kita harus melihat melalui setiap elemen tunggal, baik karena unsur sasaran adalah elemen terakhir dari array, atau elemen yang kita cari tidak benar-benar ada dalam array sama sekali. Apa skenario kasus terbaik? Nah kita mungkin menemukan elemen segera. Dan berapa banyak elemen kita kemudian harus melihat di dalam kasus terbaik, jika kita mencarinya dan kami merasa di awal? Kita bisa segera dihentikan. 

Apa yang dikatakan tentang kompleksitas pencarian linear? Nah dalam kasus terburuk, kita harus untuk melihat setiap elemen tunggal. Dan sehingga berjalan di O dari n, dalam kasus terburuk. 

Dalam kasus terbaik, kita akan menemukan elemen segera. Dan berjalan di omega dari 1. 

Aku Doug Lloyd. Ini adalah CS50.