[Bermain muzik] DOUG LLOYD: Linear carian adalah kita algoritma boleh gunakan untuk mencari satu elemen dalam array. Yang ingat algoritma adalah satu set langkah-demi-langkah arahan untuk menyiapkan tugas. 

Pencarian linear algoritma berfungsi seperti berikut. Melelar seluruh array dari kiri ke betul, mencari elemen yang ditetapkan. 

Dalam kod pseudo, yang merupakan lebih versi suling ayat ini, jika elemen pertama adalah apa yang anda cari, anda boleh berhenti. Jika tidak, bergerak ke elemen yang akan datang dan terus pergi berulang-ulang sehingga anda mencari unsur, atau anda tidak. Oleh itu, kita boleh menggunakan linear algoritma carian, sebagai contoh, untuk mencari nilai sasaran sembilan dalam pelbagai ini. Baik kita mulakan pada permulaan. Jika ia adalah apa yang kita cari, kami boleh berhenti. Ia tidak, kita tidak mencari 11. Jadi jika tidak, bergerak ke elemen seterusnya. 

Oleh itu, kita melihat 23. Adalah 23 apa yang kami cari? Yah tidak, jadi kita bergerak ke depan unsur unsur yang akan datang, dan kami terus melalui proses ini berulang-ulang dan ke atas, sehingga kita tanah pada keadaan seperti ini. 

Sembilan adalah apa yang kita cari, dan elemen ini array adalah, nilai itu adalah sembilan. Dan dengan itu kita mendapati apa yang kita cari, dan kita boleh berhenti. Pencarian linear mempunyai selesai, dengan jayanya. 

Tetapi bagaimana pula jika kita cari unsur yang bukan dalam pelbagai kami. Adakah carian linear masih berfungsi? Nah pasti. Oleh itu, kita mengulangi proses ini bermula dari elemen pertama. Jika ia adalah apa yang kita cari, kami boleh berhenti. Ianya bukan. Jika tidak, kita beralih kepada elemen seterusnya. 

Tetapi kita boleh terus mengulangi proses ini, memeriksa setiap elemen seterusnya, berharap bahawa kita mencari nombor 50. Tetapi kita tidak akan tahu jika kami telah mendapati jumlah 50 atau jika kita tidak, sehingga kita telah melangkah ke atas setiap elemen tunggal array. 

Hanya sekali yang telah kami lakukan itu dan datang sehingga pendek, boleh kita membuat kesimpulan bahawa 50 tidak ada di dalam array. Dan sebagainya carian linear algoritma, dan ia gagal, per se. Tetapi tidak dalam erti kata bahawa ia tidak berjaya melakukannya, kami bertanya ia lakukan. 

Ia tidak berjaya masuk sebagai banyak kerana ia tidak mendapati 50, tetapi 50 tidak dalam array. Tetapi kita telah mendalam dicari melalui setiap elemen tunggal dan sebagainya, sementara kami tidak menjumpai apa-apa, carian linear masih berjaya walaupun unsur bukan dalam array. 

Jadi apa kes yang paling teruk senario dengan carian linear? Baik kita perlu melihat melalui setiap elemen tunggal, sama ada kerana elemen sasaran adalah elemen terakhir array, atau unsur yang kita cari tidak benar-benar wujud dalam array sama sekali. Apakah senario kes terbaik? Baik kita mungkin mendapati unsur dengan segera. Dan berapa banyak unsur-unsur kita kemudian perlu melihat di dalam kes ini, jika kita mencari untuk itu dan kami menemuinya di awal-awal lagi? Kita boleh berhenti serta-merta. 

Apakah ini mengatakan mengenai kerumitan carian linear? Baik dalam kes paling teruk, kita ada untuk melihat setiap elemen tunggal. Dan supaya ia berjalan di O n, dalam kes yang paling teruk. 

Dalam kes ini, kita akan mencari elemen dengan segera. Dan supaya berjalan dalam omega 1. 

Saya Doug Lloyd. Ini adalah CS50.