การค้นหาข้อมูล (Searching)                     การค้นหาข้อมูลถือว่าเป็น Algorithm ที่สำคัญที่สุดเรื่องหนึ่ง ในการนำคอมพิวเตอร์ไปใช้งาน เพราะการเรียกข้อมูลจากหน่วยความจำ หรือจาก File เพื่อนำมาใช้งาน ส่วนใหญ่แล้วการค้นหาข้อมูลจะถูกประกอบเข้าเป็นส่วนหนึ่งของขบวนการทำงานด้วยคอมพิวเตอร์                                                                                                          การค้นหาข้อมูล แบ่งตามลักษณะการจัดเก็บได้ 2 อย่างคือ     1.การค้นหาข้อมูลภายใน     ( Internal Search) 2. การค้นหาข้อมูลภายนอก     ( External Search)    การค้นหาข้อมูล แบ่งตามลักษณะการค้นหาได้ 2 อย่างคือ 1. การค้นหาข้อมูล ตามลำดับ ( Linear Search)      ซึ่งการค้นหาแบบนี้มีเทคนิค 2 อย่างคือ      1.1 Unsorted Linear Search      1.2 Sorted Linear Search 2. การค้นหาข้อมูลทวิภาค ( Binary Search)      2.1 Binary Search in Array      2.2 Binary Search Tree                   หลักการ Unsorted Linear Search   เป็นการค้นหาข้อมูลแบบเรียงลำดับทีละตัว เริ่มตั้งแต่ข้อมูลตัวแรก ไปเรื่อย ๆ จนกระทั่งพบข้อมูลที่ต้องการ หรือจนหมดทุกตัว                        Algorithm Unsorted Linear Search   1. กำหนดให้ ตัวนับเริ่มต้นเป็นตัวแรกของข้อมูล 2. เปรียบเทียบข้อมูล ถ้า - พบข้อมูล ทำข้อ 5 - ไม่พบข้อมูล ทำข้อ 3 3. เพิ่มค่า ตัวนับ 4. ทำซ้ำข้อ 2 5. จบ                       Complexity Unsorted Linear Search ครั้งที่ 1 เปรียบเทียบ 1 ครั้ง ครั้งที่ 2 เปรียบเทียบ 1 ครั้ง ครั้งที่ 3 เปรียบเทียบ 1 ครั้ง ครั้งที่ 4 เปรียบเทียบ 1 ครั้ง ครั้งที่ 5 เปรียบเทียบ 1 ครั้ง ครั้งที่ 6 เปรียบเทียบ 1 ครั้ง รวม 6 ครั้ง ถ้าให้ข้อมูลมี n จำนวนจะได้ 1+ 1+1+1+1+1=6 หรือ n ครั้ง นั่นเอง ดังนั้น Complexity หรือ Big-Oh ของ Unsorted Linear Search จึงมีค่าเป็น O(n) -         Best case O(1) -         Worse case O(n)           

ถ้าให้ข้อมูลมี n จำนวนจะได้

1+ 1+1+1+1+1=6 หรือ n ครั้ง นั่นเอง ดังนั้น Complexity หรือ Big-Oh ของ Unsorted Linear Search จึงมีค่าเป็น O(n) -        Best case O(1) -        Worse case O(n)
         

 

หลักการ Sorted Linear Search   เป็นการค้นหาข้อมูลแบบเรียงลำดับทีละตัว เริ่มตั้งแต่ข้อมูลตัวแรก ไปเรื่อย ๆ จนกระทั่งพบข้อมูลที่ต้องการ หรือจนค่าของข้อมูลตัวถัดไปมีค่ามากกว่า ซึ่งมีเงื่อนไขว่า ข้อมูลนั้นต้องมีการจัดเรียงแล้วเท่านั้น              Algorithm

Sorted Linear Search

   

 

1. กำหนดให้ ตัวนับเริ่มต้นเป็นตัวแรกของข้อมูล 2. เปรียบเทียบข้อมูล ถ้า - พบข้อมูล ทำข้อ   5 - ค่าของข้อมูลที่ต้องการค้นหา < ค่าของข้อมูลที่ตำแหน่ง   ตัวนับ    ทำข้อ   5 3. เพิ่มค่า ตัวนับ 4. ทำซ้ำข้อ 2 5. จบ