[เล่นเพลง] DOUG LLOYD เป็น Linear ค้นหาเป็นอัลกอริทึมที่เรา สามารถใช้เพื่อหาองค์ประกอบในอาร์เรย์ ขั้นตอนวิธีการเรียกคืน เป็นขั้นตอนโดยขั้นตอนการตั้งค่า คำแนะนำสำหรับการงาน 

การค้นหาเชิงเส้น ขั้นตอนวิธีการทำงานดังนี้ ย้ำทั่วอาร์เรย์จากซ้ายไป ขวามองหาองค์ประกอบที่ระบุ 

ใน pseudocode ซึ่งเป็นมากขึ้น กลั่นรุ่นของประโยคนี้ ถ้าองค์ประกอบแรกเป็นสิ่งที่ คุณกำลังมองหาคุณสามารถหยุด มิฉะนั้นจะย้ายไปยังองค์ประกอบถัดไปและ ให้ไปซ้ำแล้วซ้ำจนกว่าคุณจะพบ องค์ประกอบหรือคุณทำไม่ได้ ดังนั้นเราจึงสามารถใช้เชิงเส้น วิธีการค้นหาตัวอย่างเช่น เพื่อหาค่าเป้าหมาย เก้าในอาร์เรย์นี้ ดีที่เราจะเริ่มต้นที่จุดเริ่มต้น ถ้ามันเป็นสิ่งที่เรากำลัง มองหาเราสามารถหยุด มันไม่ได้เราไม่ได้มองหา 11 ดังนั้นอย่างอื่นให้ย้ายไปยังองค์ประกอบถัดไป 

ดังนั้นเราจึงมองไปที่ 23 23 สิ่งที่เรากำลังมองหา? ไม่ดีดังนั้นเราจึงย้ายไปต่อไป องค์ประกอบและองค์ประกอบถัดไป และเราจะผ่านให้ กระบวนการนี​​้ซ้ำแล้วซ้ำอีก และมากกว่าจนกว่าเราจะลงจอด ในสถานการณ์เช่นนี้ 

เก้าคือสิ่งที่เรากำลังมองหา และองค์ประกอบของอาร์เรย์นี้ คือมันเป็นค่าเก้า และเพื่อให้เราพบว่าสิ่งที่เรากำลัง มองหาและเราสามารถหยุด การค้นหาเชิงเส้นมี เสร็จสิ้นการประสบความสำเร็จ 

แต่สิ่งที่เกี่ยวกับถ้าเรากำลังมองหา องค์ประกอบที่ไม่ได้อยู่ในอาเรย์ของเรา ไม่เชิงเส้นการค้นหายังคงทำงาน? กันนั่นเอง ดังนั้นเราจึงทำซ้ำขั้นตอนนี้ เริ่มต้นที่องค์ประกอบแรก ถ้ามันเป็นสิ่งที่เรากำลัง มองหาเราสามารถหยุด มันไม่ใช่. มิฉะนั้นเราจะย้ายไปยังองค์ประกอบถัดไป 

แต่เราสามารถเก็บซ้ำขั้นตอนนี้ การตรวจสอบองค์ประกอบในทางกลับกัน หวังว่าเราจะพบจำนวน 50 แต่เราจะไม่ทราบว่า เราพบจำนวน 50 หรือถ้าเราไม่ได้จนกว่าเราจะได้ก้าว มากกว่าทุกองค์ประกอบหนึ่งของอาร์เรย์ 

เพียงครั้งเดียวที่เราเคยทำ และเกิดขึ้นในระยะสั้น เราสามารถสรุปได้ว่า 50 ไม่ได้อยู่ในอาร์เรย์ และเพื่อให้การค้นหาเชิงเส้น ขั้นตอนวิธีการที่ดีที่จะล้มเหลวต่อ แต่ไม่ได้อยู่ในแง่ที่ว่ามัน ไม่ประสบความสำเร็จในการทำสิ่งที่ เราถามจะทำ 

มันก็ไม่ประสบความสำเร็จในการเป็น มากที่สุดเท่าที่มันไม่ได้หา 50, 50 แต่ไม่ได้อยู่ในอาร์เรย์ แต่เราได้ค้นหาอย่างละเอียดถี่ถ้วน ผ่านทุกองค์ประกอบเดียว และอื่น ๆ ในขณะที่เราไม่พบ อะไรยังคงค้นหาเชิงเส้น ประสบความสำเร็จแม้ว่า องค์ประกอบที่ไม่ได้อยู่ในอาร์เรย์ 

ดังนั้นสิ่งที่เป็นกรณีที่เลวร้ายที่สุด สถานการณ์ที่มีการค้นหาเชิงเส้น? ดีที่เราจะต้องมองผ่าน ทุกองค์ประกอบเดียว เพราะองค์ประกอบเป้าหมาย เป็นองค์ประกอบสุดท้ายของอาร์เรย์ หรือองค์ประกอบที่เรากำลังมองหาไม่ได้ มีอยู่จริงในอาร์เรย์ที่ทั้งหมด สถานการณ์กรณีที่ดีที่สุดคืออะไร? ดีที่เราอาจพบ องค์ประกอบทันที และวิธีการหลายองค์ประกอบ แล้วเราจะต้องมอง ในกรณีที่ดีที่สุด ถ้าเรากำลังมองหามัน และเราพบว่ามันที่จุดเริ่มต้นมาก? เราสามารถหยุดทันที 

นี้ไม่พูดอะไรเกี่ยวกับ ความซับซ้อนของการค้นหาเชิงเส้น? ดีในกรณีที่เลวร้ายที่สุดที่เรามี จะมองไปที่ทุกองค์ประกอบเดียว และเพื่อให้มันทำงานในโอ n ในกรณีที่เลวร้ายที่สุด 

ในกรณีที่ดีที่สุดที่เราจะ หาองค์ประกอบทันที และเพื่อให้ทำงานในโอเมก้า 1 

ฉันลอยด์ดั๊ก นี่คือ CS50