การค้นหาข้อมูล (Searching)

Introduction to Searching

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

การค้นหาข้อมูลที่มีประสิทธิภาพนั้น ขึ้นอยู่กับหลักการค้นหา รวมถึงขั้นตอนของการค้นหานั้น การค้นหาข้อมูลพื้นฐานมีหลากหลายวิธี เช่น การค้นหาข้อมูลแบบลำดับ การค้นหาข้อมูลแบบทวิภาค และการค้นหาข้อมูลแบบแฮชชิง

การค้นหาข้อมูลแบบลำดับ (Sequential Search)

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

ขั้นตอนการค้นหาข้อมูลแบบลำดับ มีดังนี้

1.            ให้ข้อมูลตัวแรกของข้อมูลที่นำมาค้นหา เป็นข้อมูลพิจารณา

2.            นำข้อมูลตัวที่ต้องการค้นหาไปเปรียบเทียบว่าเท่ากับข้อมูลที่พิจารณาหรือไม่

                         -ถ้าเท่ากัน แสดงว่าพบข้อมูลตัวที่ต้องการค้นหาในตำแหน่งของข้อมูลที่พิจารณา ซึ่งถือว่าการค้นหาสมบูรณ์
                         -ถ้าไม่เท่ากัน ให้นำข้อมูลลำดับถัดไปจากข้อมูลที่พิจารณาไปเป็นข้อมูลที่พิจารณา แล้วกลับไปทำข้อ 2
 

จากข้อมูลต่อไปนี้ จงค้นหาข้อมูล 14 ด้วยวิธีการค้นหาข้อมูลแบบลำดับ

44, 17, 40, 32, 11, 14, 28, 24  Key = 14

รอบที่ 1 Key ≠ Data[0]     

   

                                             14 ≠44

รอบที่ 2 Key ≠ Data[1]        

                                                                   14

รอบที่ 3 Key ≠ Data[2]   

                                                                                 14 ≠40

รอบที่ 4 Key ≠ Data[3]   

                                                                                                   14 ≠32

รอบที่ 5 Key ≠ Data[4]   

                                                                                                                    14 ≠11

รอบที่ 6 Key = Data[5]  14 ≠14

                                                                                                                                      14 ≠14

การค้นหาข้อมูลแบบทวิภาค (Binary Search)

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

การค้นหาข้อมูลแบบทวิภาค (Binary Search)

       มีตัวแปรที่เกี่ยวข้องอยู่ 3 ตัวแปร คือ

             

             1. ตัวแปร First หรือ ตำแหน่งเริ่มต้น เป็นตัวแปรที่ใช้สำหรับกำหนดตำแหน่งเริ่มต้น

             2. ตัวแปร Mid หรือ ตำแหน่งกึ่งกลาง ใช้สำหรับกำหนดตำแหน่งกึ่งกลาง

             3. ตัวแปร Last หรือ ตำแหน่งสุดท้าย ใช้กำหนดตำแหน่งสุดท้ายของลิสต์

การค้นหาข้อมูลแบบทวิภาค (Binary Search)

1.            หาตำแหน่งกึ่งกลางของข้อมูล เพื่อแบ่งข้อมูลออกเป็นสองส่วน

2.            นำข้อมูลตัวที่ต้องการค้นหาไปเปรียบเทียบว่าเท่ากับค่าของตำแหน่งกึ่งกลางหรือไม่

                           -ถ้าเท่ากัน แสดงว่า พบข้อมูลที่ต้องการค้นหาในตำแหน่งกึ่งกลาง ซึ่งถือว่าการ ค้นหาเสร็จสมบูรณ์

                           -ถ้าไม่เท่ากัน ให้เปรียบเทียบค่าที่ต้องการค้นหามีค่ามากกว่าค่าในตำแหน่งกึ่งกลางหรือไม่

                           -ถ้ามากกว่า ให้ข้อมูลที่นำมาค้นหา คือข้อมูลทางด้านขวาของตำแหน่งกึ่งกลาง

จากข้อมูลต่อไปนี้ จงค้นหาข้อมูล 28 ด้วยวิธีค้นหาแบบทวิภาค

               

            11, 14, 17, 24, 28, 32, 40, 44        Key = 28       

รอบที่ 1           Mid      = (First + Last) / 2

                                    = (0+7)/2

                                    = 3

                                                                    First                            Mid                                     Last

Key > data[mid] เพราะฉะนั้น First = [4] และ Last = [7]

รอบที่ 2           Mid      = (First + Last) / 2

                                    = (4+7)/2

                                    = 5

                                                                                                                  First     Mid               Last

Key < data[mid] เพราะฉะนั้น First = [4] และ Last = [4]

รอบที่ 3           Mid      = (First + Last) / 2

                                    = (4+4)/2

                                    = 4

                                                                                                                 First         

                                                                                                                 Mid         

                                                                                                                 Last

Key < data[mid] เพราะฉะนั้นพบข้อมูลที่ดรรชนี เท่ากับ 4

Binary Search tree   มีคุณสมบัติดังนี้

•  ทรีย่อยทางซ้าย หรือโหนดทางซ้ายทุกตัวต้องมีค่าน้อยกว่ารูทโหนด
• 2  ทรีย่อยทางขวาหรือโหนดทางขวาทุกตัวต้องมีค่ามากกว่าหรือเท่ากับรูทโหนด
• 3  ทุก ๆ ทรีย่อย ต้องเป็นไบนารีเสิร์ชทรี

การค้นหา

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

การค้นหาข้อมูลแบบแฮชชิง (Hashing Search)

การค้นหาข้อมูลแบบแฮชชิง หมายถึง การค้นหาข้อมูลที่ถูกจัดเก็บในตารางแฮช (Hash Table) โดยการนำคีย์ข้อมูล (Key) ที่ต้องการค้นหาไปผ่านกระบวนแฮช (Hash Function) เพื่อให้ทราบตำแหน่งที่ใช้ในการเก็บข้อมูล

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

            กระบวนการแฮช คือ การแปลงค่าคีย์ข้อมูลให้กลายเป็นตำแหน่งที่ใช้ในการจัดเก็บข้อมูลในตารางแฮช ซึ่งมีหลายวิธีด้วยกัน แต่วิธีที่นิยมใช้กันมาก คือ วิธีมอดุโลดิวิชั่น (Modulo Division) ซึ่งเป็นวิธีที่นำค่าคีย์ข้อมูลมาหารแบบมอดุโล (Modulo : %) ด้วยขนาดของตารางที่ใช้ในการเก็บข้อมูล

การเก็บข้อมูลในตารางแฮช จะมีข้อเสีย คือ มีการชนกันของข้อมูล (Collision) กล่าวคือ คีย์ข้อมูลต่าง ๆ เมื่อนำมาผ่านกระบวนการแฮชแล้วได้ตำแหน่งข้อมูลเดียวกัน