บทนำสู่อัลกอริธึมการค้นหาเชิงเส้น: บทนำและคุณลักษณะ[พร้อมตัวอย่าง]

การค้นหาคืออะไร?

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

โครงสร้างข้อมูลช่วยให้สามารถค้นหาข้อมูลได้สองวิธี

1. การค้นหาเชิงเส้นหรือการค้นหาตามลำดับ
2. ค้นหาไบนารี

ค้นหาเชิงเส้น

อัลกอริธึมการค้นหาเชิงเส้นเป็นประเภทของอัลกอริทึมสำหรับการค้นหาข้อมูลตามลำดับ อัลกอริธึมนี้ค้นหาองค์ประกอบที่กำหนดซึ่งมีความซับซ้อน O(n) มันถูกนำไปใช้กับคอลเลกชันของรายการ แต่ละรายการของข้อมูลจะถูกค้นหาตามลำดับ และส่งคืนหากตรงกับองค์ประกอบที่ค้นหา หากไม่พบรายการที่ตรงกัน การค้นหาจะดำเนินต่อไปจนถึงสิ้นสุดข้อมูลที่รวบรวมไว้ โดยพื้นฐานแล้วเป็นเทคนิคในการสำรวจทุกองค์ประกอบขณะสำรวจรายการ อัลกอริธึมการค้นหาสามารถใช้ได้กับทั้งข้อมูลที่เรียงลำดับแล้วและไม่ได้เรียงลำดับ การค้นหาเชิงเส้นในทางปฏิบัตินั้นไม่ค่อยได้ใช้ เนื่องจากมีตัวเลือกการค้นหาที่เร็วกว่าโดยอัลกอริธึมการค้นหาอื่นๆ เช่น อัลกอริธึมการค้นหาแบบไบนารีและตารางแฮช

ขั้นตอนในอัลกอริธึมการค้นหาเชิงเส้น

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

คุณสมบัติของอัลกอริธึมการค้นหาเชิงเส้น

1. มักใช้กับรายการข้อมูลที่ไม่เรียงลำดับหรือไม่เรียงลำดับเพียงเล็กน้อย
2. เวลาขึ้นอยู่กับจำนวนขององค์ประกอบเป็นเส้นตรง ดังนั้นจึงมีความซับซ้อนของเวลาหาก O(n)
3. การนำไปใช้นั้นง่ายมาก

อัลกอริธึมการค้นหาเชิงเส้น

วิธีการวนซ้ำแบบต่อเนื่องจะดำเนินต่อไปเว้นแต่และจนกว่าจะพบรายการ

• อัลกอริทึม Seqnl_Search (รายการ รายการ)
• พื้นฐาน: list != ;
• โพสต์: ส่งคืนดัชนีของรายการหากพบ มิฉะนั้น: 1
• ดัชนี <- fi
• ในขณะที่ดัชนี < list.Cnt และ list[index] != item //cnt: ตัวนับตัวแปร
• ดัชนี <- ดัชนี + 1
• สิ้นสุดในขณะที่
• ถ้าดัชนี < list.Cnt และ list[index] = item
• ดัชนีผลตอบแทน
• สิ้นสุด if
• ผลตอบแทน: 1
• สิ้นสุด Seqnl_Search

ตัวอย่างการค้นหาเชิงเส้น

ปัญหา: กำหนดอาร์เรย์ arr[] ของ n องค์ประกอบ ให้เขียนฟังก์ชันเพื่อค้นหาองค์ประกอบ x ที่กำหนดใน arr[]

รูปที่ 1: ตัวอย่างโค้ดที่แสดงการใช้งานอัลกอริธึมการค้นหาเชิงเส้น

แหล่งที่มา

อัลกอริธึมการค้นหาเชิงเส้นสามารถใช้ได้ในภาษาการเขียนโปรแกรมหลายภาษา

1. การค้นหาเชิงเส้นใน Python

รูปที่ 2: ตัวอย่างโค้ดที่แสดงอัลกอริธึมการค้นหาเชิงเส้นในภาษา Python

แหล่งที่มา

ผลลัพธ์: มีองค์ประกอบอยู่ที่ดัชนี 3

2. การค้นหาเชิงเส้นใน C

รูปที่ 3: ตัวอย่างโค้ดที่แสดงอัลกอริธึมการค้นหาเชิงเส้นในภาษาซี

แหล่งที่มา

ผลลัพธ์ : มีองค์ประกอบอยู่ที่ดัชนี 3

3. การค้นหาเชิงเส้นในโครงสร้างข้อมูล

Pseudocode สำหรับปัญหาการค้นหาเชิงเส้นในโครงสร้างข้อมูลคือ

รูปที่ 4: รหัสเทียมสำหรับอัลกอริธึมการค้นหาเชิงเส้น

แหล่งที่มา

ค้นหาไบนารี

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

อัลกอริทึมการค้นหาแบบไบนารีมีขั้นตอนต่อไปนี้

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

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

คุณสมบัติของการค้นหาไบนารี

• อัลกอริทึมการค้นหาแบบไบนารีมีประโยชน์สำหรับการค้นหาองค์ประกอบจำนวนมากในอาร์เรย์
• อัลกอริธึมการค้นหาแบบไบนารีมีความซับซ้อนของเวลาเป็น O(logn)
• การใช้อัลกอริธึมการค้นหาแบบไบนารีนั้นง่าย

อัลกอริทึมการค้นหาไบนารี

• อัลกอริทึม Binary_Search (รายการ รายการ)
• ตั้งค่า L เป็น 0 และ R เป็น n: 1
• ถ้า L > R ดังนั้น Binary_Search จะหยุดทำงานไม่สำเร็จ
• อื่น
• ตั้งค่า m (ตำแหน่งในองค์ประกอบกลาง) ไปที่พื้นของ (L + R) / 2
• ถ้า Am < T ให้ตั้งค่า L เป็น m + 1 และไปที่ขั้นตอนที่ 3
• ถ้า Am > T ให้ตั้งค่า R เป็น m: 1 และไปที่ขั้นตอนที่ 3
• ตอนนี้ Am = T
• การค้นหาเสร็จสิ้น ผลตอบแทน (ม.)

บทสรุป

ในบทความนี้ เราได้พิจารณาว่าอัลกอริธึมการค้นหาเชิงเส้นคืออะไร และยังศึกษารายละเอียดวิธีค้นหาองค์ประกอบจากรายการโดยใช้อัลกอริธึมการค้นหาเชิงเส้น สุดท้ายนี้ เรายังได้เห็นวิธีที่เราสามารถปรับใช้ Linear Search Algorithm โดยใช้ Python 3 เป็นภาษาและรับผลลัพธ์ที่ต้องการได้

หากคุณสนใจ Data Science คุณต้องลองดู IIIT-B และ Executive PG Program ของ upGrad ใน Data Science ซึ่งได้รับการสร้างขึ้นมาอย่างพิถีพิถันสำหรับมืออาชีพที่ทำงานและมีกรณีศึกษามากมาย เวิร์กช็อปภาคปฏิบัติ การให้คำปรึกษาแบบตัวต่อตัว และ ล้นหลาม.