>> [เล่นเพลง]
DOUG LLOYD เป็น Linear ค้นหาเป็นอัลกอริทึมที่เรา
สามารถใช้เพื่อหาองค์ประกอบในอาร์เรย์
ขั้นตอนวิธีการเรียกคืน เป็นขั้นตอนโดยขั้นตอนการตั้งค่า
คำแนะนำสำหรับการงาน
>> การค้นหาเชิงเส้น ขั้นตอนวิธีการทำงานดังนี้
ย้ำทั่วอาร์เรย์จากซ้ายไป ขวามองหาองค์ประกอบที่ระบุ
>> ใน pseudocode ซึ่งเป็นมากขึ้น กลั่นรุ่นของประโยคนี้
ถ้าองค์ประกอบแรกเป็นสิ่งที่ คุณกำลังมองหาคุณสามารถหยุด
มิฉะนั้นจะย้ายไปยังองค์ประกอบถัดไปและ ให้ไปซ้ำแล้วซ้ำจนกว่าคุณจะพบ
องค์ประกอบหรือคุณทำไม่ได้
ดังนั้นเราจึงสามารถใช้เชิงเส้น วิธีการค้นหาตัวอย่างเช่น
เพื่อหาค่าเป้าหมาย เก้าในอาร์เรย์นี้
ดีที่เราจะเริ่มต้นที่จุดเริ่มต้น
ถ้ามันเป็นสิ่งที่เรากำลัง มองหาเราสามารถหยุด
มันไม่ได้เราไม่ได้มองหา 11
ดังนั้นอย่างอื่นให้ย้ายไปยังองค์ประกอบถัดไป
>> ดังนั้นเราจึงมองไปที่ 23
23 สิ่งที่เรากำลังมองหา?
ไม่ดีดังนั้นเราจึงย้ายไปต่อไป องค์ประกอบและองค์ประกอบถัดไป
และเราจะผ่านให้ กระบวนการนี​​้ซ้ำแล้วซ้ำอีก
และมากกว่าจนกว่าเราจะลงจอด ในสถานการณ์เช่นนี้
>> เก้าคือสิ่งที่เรากำลังมองหา และองค์ประกอบของอาร์เรย์นี้
คือมันเป็นค่าเก้า
และเพื่อให้เราพบว่าสิ่งที่เรากำลัง มองหาและเราสามารถหยุด
การค้นหาเชิงเส้นมี เสร็จสิ้นการประสบความสำเร็จ
>> แต่สิ่งที่เกี่ยวกับถ้าเรากำลังมองหา องค์ประกอบที่ไม่ได้อยู่ในอาเรย์ของเรา
ไม่เชิงเส้นการค้นหายังคงทำงาน?
กันนั่นเอง
ดังนั้นเราจึงทำซ้ำขั้นตอนนี้ เริ่มต้นที่องค์ประกอบแรก
ถ้ามันเป็นสิ่งที่เรากำลัง มองหาเราสามารถหยุด
มันไม่ใช่.
มิฉะนั้นเราจะย้ายไปยังองค์ประกอบถัดไป
>> แต่เราสามารถเก็บซ้ำขั้นตอนนี้ การตรวจสอบองค์ประกอบในทางกลับกัน
หวังว่าเราจะพบจำนวน 50
แต่เราจะไม่ทราบว่า เราพบจำนวน 50
หรือถ้าเราไม่ได้จนกว่าเราจะได้ก้าว มากกว่าทุกองค์ประกอบหนึ่งของอาร์เรย์
>> เพียงครั้งเดียวที่เราเคยทำ และเกิดขึ้นในระยะสั้น
เราสามารถสรุปได้ว่า 50 ไม่ได้อยู่ในอาร์เรย์
และเพื่อให้การค้นหาเชิงเส้น ขั้นตอนวิธีการที่ดีที่จะล้มเหลวต่อ
แต่ไม่ได้อยู่ในแง่ที่ว่ามัน ไม่ประสบความสำเร็จในการทำสิ่งที่
เราถามจะทำ
>> มันก็ไม่ประสบความสำเร็จในการเป็น มากที่สุดเท่าที่มันไม่ได้หา 50,
50 แต่ไม่ได้อยู่ในอาร์เรย์
แต่เราได้ค้นหาอย่างละเอียดถี่ถ้วน ผ่านทุกองค์ประกอบเดียว
และอื่น ๆ ในขณะที่เราไม่พบ อะไรยังคงค้นหาเชิงเส้น
ประสบความสำเร็จแม้ว่า องค์ประกอบที่ไม่ได้อยู่ในอาร์เรย์
>> ดังนั้นสิ่งที่เป็นกรณีที่เลวร้ายที่สุด สถานการณ์ที่มีการค้นหาเชิงเส้น?
ดีที่เราจะต้องมองผ่าน ทุกองค์ประกอบเดียว
เพราะองค์ประกอบเป้าหมาย เป็นองค์ประกอบสุดท้ายของอาร์เรย์
หรือองค์ประกอบที่เรากำลังมองหาไม่ได้ มีอยู่จริงในอาร์เรย์ที่ทั้งหมด
สถานการณ์กรณีที่ดีที่สุดคืออะไร?
ดีที่เราอาจพบ องค์ประกอบทันที
และวิธีการหลายองค์ประกอบ แล้วเราจะต้องมอง
ในกรณีที่ดีที่สุด ถ้าเรากำลังมองหามัน
และเราพบว่ามันที่จุดเริ่มต้นมาก?
เราสามารถหยุดทันที
>> นี้ไม่พูดอะไรเกี่ยวกับ ความซับซ้อนของการค้นหาเชิงเส้น?
ดีในกรณีที่เลวร้ายที่สุดที่เรามี จะมองไปที่ทุกองค์ประกอบเดียว
และเพื่อให้มันทำงานในโอ n ในกรณีที่เลวร้ายที่สุด
>> ในกรณีที่ดีที่สุดที่เราจะ หาองค์ประกอบทันที
และเพื่อให้ทำงานในโอเมก้า 1
>> ฉันลอยด์ดั๊ก
นี่คือ CS50