DTS 11-16-09-2552

สรุป Searching

การค้นหาข้อมูล (searching)
แบ่งเป็น 2 ประเภท คือ
1.การค้นหาข้อมูลแบบภายใน
2.การค้นหาข้อมูลแบบภายนอก


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

ตัวอย่าง เช่น มีข้อมูลอยู่ 10 จำนวน ดังนี้

18 3 39 70 27 8 1 31 2 50

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


การค้นหาแบบเซนทินัล(Sentinel)
เป็นวิธีที่การค้นหาแบบเดียวกับวิธีการค้นหาแบบเชิงเส้นแต่ประสิทธิภาพดีกว่า
ตรงที่เปรียบเทียบน้อยครั้งกว่า วิธีการ คือ
1. เพิ่มขนาดของแถวลำดับ ที่ใช้เก็บข้อมูลอีก 1 ที่
2. นำข้อมูลที่จะใช้ค้นหาข้อมูลใน Array ไปฝากที่ต้นหรือ ท้าย Array
3. ตรวจสอบผลลัพธ์จากการหา โดยตรวจสอบจากตำแหน่งที่พบ ถ้าตำแหน่งที่พบมีค่าเท่ากับ n-1แสดงว่าหาไม่พบนอกนั้นถือว่าพบข้อมูลที่ค้าหา




การค้นหาแบบไบนารี (Binary Search)
เป็นวิธีการค้นหาข้อมูลที่รวดเร็วกว่าการค้นหาแบบเรียงลำดับ แต่วิธีนี้ใช้ได้ในกรณีที่ข้อมูลถูกจัดเก็บแบบเรียงลำดับเรียบร้อยแล้ว โดยอาจจะเรียงลำดับจากน้อยไปมากหรือจากมากไปน้อย การค้นหาข้อมูลด้วยวิธีนี้ ในการเปรียบเทียบแต่ละครั้งสามารถลดจำนวนข้อมูลที่ต้องเปรียบเทียบได้คราวละประมาณครึ่งหนี่งของที่เหลือ
โดยการค้นหาข้อมูลแบบทวิภาคเริ่มต้นด้วยการหาว่าตำแหน่งกึ่งกลางของ ข้อมูลทั้งหมดอยู่ที่ตำแหน่งใด
เนื่องจากข้อมูลทั้งหมดมีการเรียงลำดับค่า ถ้าเรียงจากน้อยไปมาก ข้อมูลที่ตำแหน่งกึ่งกลางจะแบ่งข้อมูลเป็น 2 ส่วน ส่วนแรกเป็นข้อมูลที่มีค่าน้อยกว่าค่าที่ตำแหน่งกึ่งกลาง และส่วนที่ 2 เป็นข้อมูลที่มีค่ามากกว่าค่าที่ตำแหน่ง กึ่งกลาง

สูตรในการค้นหาตำแหน่งตัวเเทน คือ
mid = (low+high)/2mid คือ ตำแหน่งกลาง
low คือ ตำแหน่งต้นแถวลำดับ
high คือ ตำแหน่งท้ายของแถวลำดับ