เฉลยกิจกรรมที่ 2.10 ค้นข้อมูล บทที่ 2 การแก้ปัญหาและขั้นตอนวิธี หน้า 57 วิชาวิทยาการคำนวณ
ดูตัวอย่างการเขียนโปรแกรมนี้ด้วยภาษา Python >> (คลิก)
พิจารณารายการข้อมูลต่อไปนี้
8, 9, 13, 35, 42, 44, 50, 54, 58, 60, 61, 62, 77, 84, 86, 90, 92, 96
ให้เขียนข้อมูลจากรายการลงในตารางด้านล่างให้ตรงตามดัชนีในแถวแรก
| ดัชนี | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| ข้อมูล | 58 |
จากนั้นให้แสดงการทำงานของขั้นตอนวิธีในการหา 62 ในรายการดังกล่าว โดยเติมค่าตัวแปรเมื่อเริ่มต้นการทำงานในแต่ละรอบ
n = _______________
| รอบที่ | left | right | mid | x | ผลการเปรียบเทียบกับ target |
|---|---|---|---|---|---|
| 1 | 1 | 18 | 9 | 58 | น้อยกว่า |
| 2 | 10 | 18 | |||
| 3 | |||||
| 4 | |||||
| 5 |
จากโจทย์จะเป็นการค้นหาข้อมูลในแบบทวิภาค (Binary Search) ซึ่งเราต้องทำความรู้จักกับคำศัพท์และตัวแปรต่างๆ ที่เกี่ยวข้องก่อน
- ดัชนี หรือ index คือตำแหน่งของข้อมูล เช่น 58 คือข้อมูลที่อยู่ในดัชนีที่ 9 นั่นแปลว่า 58 อยู่ในตำแหน่งที่ 9 ของชุดข้อมูลนั่นเอง
- n คือจำนวนของข้อมูล ในที่นี้คือ 18
- left คือตำแหน่งเริ่มต้นที่จะค้นหาข้อมูล หากเริ่มต้นค้นหาข้อมูลที่ตำแหน่งที่ 1 left ก็จะเท่ากับ 1
- right คือตำแหน่งสุดท้ายที่จะค้นหาข้อมูล เช่น จะค้นหาข้อมูลตั้งแต่ตำแหน่งที่ 1 – 18 ,, right ก็จะเท่ากับ 18
- mid คือตำแหน่งตรงกลางของช่วงที่จะค้นหา เช่น ค้นหาข้อมูลตั้งแต่ตำแหน่ง 1 – 18 ก็ต้องหาตำแหน่งตรงกลางที่อยู่ระหว่าง 1 – 18 วิธีคิดง่ายๆ คือ เอาตำแหน่งแรก บวกด้วยตำแหน่งสุดท้าย หารด้วย 2 ปัดเศษทิ้ง ตัวอย่าง (1+18) ÷ 2 = 9.5 ปัดเศษทิ้ง จะได้ 9 เพราะฉะนั้น 9 คือตำแหน่งตรงกลางระหว่าง 1 – 18 นั่นเอง
- x คือ ค่าที่อยู่ในดัชนี mid หรือตำแหน่งตรงกลาง เช่น ในรอบแรกเราหา mid ได้ 9 ,, x ก็คือข้อมูลที่อยู่ในดัชนีที่ 9 นั่นคือ 58
- target คือ ค่าที่เราต้องการค้นหา ซึ่งโจทย์ระบุว่าหา 62 เพราะฉะนั้น target = 62
เมื่อเรารู้จักกับคำศัพท์และตัวแปรที่เกี่ยวข้องเรียบร้อยแล้ว ก็มาเริ่มทำกันเลย !!
1. ในส่วนแรก ให้เราเติมข้อมูลให้ตรงกับดัชนีต่างๆ ที่โจทย์ระบุให้เรียบร้อยดังเช่นตารางด้านล่าง
| ดัชนี | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| ข้อมูล | 8 | 9 | 13 | 35 | 42 | 44 | 50 | 54 | 58 | 60 | 61 | 62 | 77 | 84 | 86 | 90 | 92 | 96 |
2. โจทย์ถามถึง n ว่าเท่ากับเท่าไหร่ n คือจำนวนของข้อมูล ในที่นี้ข้อมูลมีทั้งหมด 18 ตัว เพราะฉะนั้น n = 18
3. โจทย์ให้เติมคำตอบต่างๆ ลงไปในตาราง ซึ่งมีตัวอย่างมาให้เล็กน้อย
| รอบที่ | left | right | mid | x | ผลการเปรียบเทียบกับ target |
|---|---|---|---|---|---|
| 1 | 1 | 18 | 9 | 58 | น้อยกว่า |
| 2 | 10 | 18 | | | |
ก่อนอื่นต้องทำความเข้าใจกับการค้นหาข้อมูลแบบทวิภาค (Binary Search) ซึ่งสามารถศึกษาด้วยตนเองได้ในหนังสือวิทยาการคำนวณ ม.4 หน้า 55 ซึ่งสามารถอธิบายวิธีการคร่าวๆ โดยอิงจากโจทย์ได้ดังนี้
1. ให้เราทำการกำหนดช่วงของการค้นหา ซึ่งครั้งแรกนั้น จะเป็นการค้นหาตั้งแต่ตำแหน่งแรกจนไปถึงตำแหน่งสุดท้าย ในที่นี้ก็จะเป็นการค้นหาข้อมูลตั้งแต่ตำแหน่งที่ 1 – 18 เพราะฉะนั้น ค่า left = 1 และ right = 18
| left | right | |||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ดัชนี | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| ข้อมูล | 8 | 9 | 13 | 35 | 42 | 44 | 50 | 54 | 58 | 60 | 61 | 62 | 77 | 84 | 86 | 90 | 92 | 96 |
2. หลังจากกำหนดช่วงแล้ว ให้ทำการหาตำแหน่งตรงกลางของช่วง โดยการนำค่า (left+right) ÷ 2 แล้วทำการปัดเศษทิ้ง ในการค้นหารอบแรก เราจะได้ตำแหน่งตรงกลางคือ 9 เพราะฉะนั้นค่า mid = 9
| left | mid | right | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ดัชนี | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| ข้อมูล | 8 | 9 | 13 | 35 | 42 | 44 | 50 | 54 | 58 | 60 | 61 | 62 | 77 | 84 | 86 | 90 | 92 | 96 |
3. เติมค่า x โดยการนำข้อมูลที่อยู่ในตำแหน่ง mid ซึ่งรอบแรกเป็นข้อมูลในตำแหน่งที่ 9 เพราะฉะนั้น x = 58
| left | mid | right | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ดัชนี | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| ข้อมูล | 8 | 9 | 13 | 35 | 42 | 44 | 50 | 54 | x = 58 | 60 | 61 | 62 | 77 | 84 | 86 | 90 | 92 | 96 |
4. ทำการเทียบ x กับ target x ในรอบแรกซึ่ง เท่ากับ 58 ส่วน target คือค่าที่ต้องการค้นหา นั่นคือ 62 เมื่อเทียบกันแล้วจะพบว่า x < target เพราะฉะนั้น จึงเขียนผลการเปรียบเทียบกับ target ในรอบแรกว่า “น้อยกว่า” นั่นเอง
| รอบที่ | left | right | mid | x | ผลการเปรียบเทียบกับ target |
|---|---|---|---|---|---|
| 1 | 1 | 18 | 9 | 58 | น้อยกว่า |
ผลการเปรียบเทียบนั้นถือว่ามีความสำคัญ เพราะ เนื่องจากการค้นหาแบบทวิภาคนั้น เงื่อนไขคือ ชุดข้อมูลนั้นต้องมีการเรียงลำดับมาแล้วเท่านั้น ซึ่งจะสังเกตเห็นได้ว่าชุดข้อมูลจากโจทน์นั้นเรียงลำดับจาก น้อยไปมาก เมื่อเราพบว่าข้อมูลตรงกลางนั้นยังไม่ใช่ข้อมูลที่ต้องการเราสามารถตัดสินได้ 2 แบบคือ
1. หากพบว่าข้อมูลกลางนั้นน้อยกว่าข้อมูลที่ต้องการค้นหา แสดงว่า ข้อมูลที่อยู่ตั้งแต่ตำแหน่งเริ่มต้น จนถึงค่ากลางนั้น น้อยกว่าค่าที่เราต้องการค้นหาทั้งหมด เช่น จากโจทย์นั้น เราพบว่าข้อมูลตรงกลางที่อยู่ในตำแหน่งที่ 9 นั้น มันน้อยกว่าค่าที่เราต้องการค้นหา เพราะฉะนั้น ข้อมูลตั้งแต่ตำแหน่งที่ 1 – 9 พูดง่ายๆ คือตั้งแต่ตำแหน่งแรก จนไปถึงตำแหน่งตรงกลางนั้น ข้อมูลทุกตัวจะน้อยกว่าข้อมูลที่เราต้องการค้นหาทั้งหมด เราจึงสามารถตัดข้อมูลเหล่านั้น ซึ่งคือตำแหน่งที่ 1 – 9 ทิ้งไป แล้วกำหนดช่วงในการค้นหาใหม่เป็น 10 – 18 แทน หรือพูดง่ายๆ คือเปลี่ยนค่า left ให้เป็นค่า mid+1
2. หากพบว่าข้อมูลกลางนั้นมากกว่าข้อมูลที่ต้องการค้นหา แสดงว่า ข้อมูลตั้งแต่ตำแหน่งตรงกลางจนไปถึงตำแหน่งสุดท้ายนั้น มากกว่าข้อมูลที่เราต้องการค้นหาอย่างแน่นอน เราจึงสามารถตัดข้อมูลเหล่านั้นทิ้งไปได้ เช่น ค้นหาข้อมูลตำแหน่งที่ 1 – 18 ตำแหน่งตรงกลางคือ 9 แล้วพบว่า ข้อมูลตำแหน่งที่ 9 นั้นมากกว่าข้อมูลที่ต้องการค้นหา ในรอบถัดไปเราก็จะกำหนดช่วงในการค้นหาใหม่เป็น 1 – 8 แทน เพราะว่าข้อมูลทุกตัวในตำแหน่งที่ 9 – 18 นั้นมากกว่าข้อมูลที่เราต้องการค้นหาแน่นอน พูดง่ายๆ คือเปลี่ยนค่า right ให้เป็น mid-1
กลับมาที่โจทย์ของเรา ซึ่งในรอบแรกเราพบว่าข้อมูลในตำแหน่งตรงกลางนั้นน้อยกว่า target แสดงว่า ข้อมูลในตำแหน่งที่ left จนไปถึง mid หรือตั้งแต่ 1 – 9 นั้น น้อยกว่า target แน่นอน ( สังเกตุได้จากข้อมูลที่เป็นสีแดงในตารางด้านล่างนั้นจะน้อยกว่า target หรือ 62 ทั้งสิ้น )
| left | mid | right | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ดัชนี | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| ข้อมูล | 8 | 9 | 13 | 35 | 42 | 44 | 50 | 54 | 58 | 60 | 61 | 62 | 77 | 84 | 86 | 90 | 92 | 96 |
เพราะฉะนั้น ในการค้นหารอบถัดไป ซึ่งคือรอบที่ 2 เราสามารถตัดข้อมูลดังกล่าวออกไปจากชุดข้อมูลได้ทันที แล้วทำการเลื่อนช่วงของการค้นหาให้แคบลง โดยเลื่อน left ไปที่ตำแหน่งแรกของชุดข้อมูลที่เราตัดส่วนที่ไม่ต้องการทิ้งไปแล้วแล้ว ซึ่ง left จะกลายเป็นตำแหน่งที่ 10 ส่วน right จะอยู่ที่เดิมคือ 18 พูดง่ายๆ ว่าเราเลื่อนช่วงของการค้นหามาเป็นดัชนีที่ 10 – 18 แทน ดังตารางด้านล่าง
| left | right | ||||||||
| ดัชนี | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| ข้อมูล | 60 | 61 | 62 | 77 | 84 | 86 | 90 | 92 | 96 |
การค้นหาในรอบที่ 2 จะสังเกตเห็นว่าโจทย์ใส่ค่าของ left และ right นั่คือ 10 และ 18 มาให้ด้วย ซึ่งตรงกับส่วนที่เราตัดพอดี
| รอบที่ | left | right | mid | x | ผลการเปรียบเทียบกับ target |
|---|---|---|---|---|---|
| 1 | 1 | 18 | 9 | 58 | น้อยกว่า |
| 2 | 10 | 18 | | | |
ให้เราทำการหาค่ากลาง ดังเช่นในรอบที่ 1 ซึ่งมีค่าเท่ากับ (10+18) ÷ 2 = 14 เพราะฉะนั้น mid = 14 และ x =84 โดยผลของการเปรียบเทียบนั้น x มีค่ามากกว่า target
| รอบที่ | left | right | mid | x | ผลการเปรียบเทียบกับ target |
|---|---|---|---|---|---|
| 1 | 1 | 18 | 9 | 58 | น้อยกว่า |
| 2 | 10 | 18 | 14 | 84 | มากกว่า |
ดังที่ได้อธิบายไว้ข้างต้นแล้ว หากเราพบว่าข้อมูลตรงกลางนั้นมีค่ามากกว่า target ให้เราทำการตัดข้อมูลตั้งแต่ตำแหน่งตรงกลางจนไปถึงตำแหน่งสุดท้ายของช่วงที่เราค้นหาทิ้งไป แล้วทำการเปลี่ยนค่า right ให้เป็นตำแหน่งสุดท้ายของช่วงที่เราเหลืออยู่ นั่นคือดัชนีที่ 10 – 13
| left | right | |||
| ดัชนี | 10 | 11 | 12 | 13 |
| ข้อมูล | 60 | 61 | 62 | 77 |
การค้นหาในรอบที่ 3 นั้นเราจึงทำการกำหนดค่า left = 10 , right = 13 , mid = (10+13) ÷ 2 = 11.5 ปัดเศษทิ้งเท่ากับ 11 , x = 61
| รอบที่ | left | right | mid | x | ผลการเปรียบเทียบกับ target |
|---|---|---|---|---|---|
| 1 | 1 | 18 | 9 | 58 | น้อยกว่า |
| 2 | 10 | 18 | 14 | 84 | มากกว่า |
| 3 | 10 | 13 | 11 | 61 | น้อยกว่า |
การค้นหาในรอบที่ 3 นั้น ข้อมูลตรงกลางนั้นน้อยกว่า target เพราะฉะนั้นเราสามารถตัดข้อมูลตั้งแต่ดัชนีที่ 10 – 11 ทิ้งไปได้ ซึ่งจะได้ช่วงใหม่คือดัชนีที่ 12 – 13
| left | right | |
| ดัชนี | 12 | 13 |
| ข้อมูล | 62 | 77 |
การค้นหาในรอบที่ 4 นั้น left = 12 , right = 13 , mid = mid = (12+13) ÷ 2 = 12.5 ปัดเศษ เหลือ 12 , x = 62
| รอบที่ | left | right | mid | x | ผลการเปรียบเทียบกับ target |
|---|---|---|---|---|---|
| 1 | 1 | 18 | 9 | 58 | น้อยกว่า |
| 2 | 10 | 18 | 14 | 84 | มากกว่า |
| 3 | 10 | 13 | 11 | 61 | น้อยกว่า |
| 4 | 12 | 13 | 12 | 62 | เท่ากับ |
ซึ่งเราพบว่าในรอบที่ 4 นั้น ข้อมูลในตำแหน่งตรงกลางหรือดัชนีที่ 12 นั้น มีค่าเท่ากับ target คือ 62 เพราะฉะนั้น การค้นหาในรอบที่ 4 จึงเป็นรอบสุดท้ายของการค้นหาในรูปแบบทวิภาคนั่นเอง
เราจึงสรุปคำตอบได้ดังนี้
| ดัชนี | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
| ข้อมูล | 8 | 9 | 13 | 35 | 42 | 44 | 50 | 54 | 58 | 60 | 61 | 62 | 77 | 84 | 86 | 90 | 92 | 96 |
n = 18
| รอบที่ | left | right | mid | x | ผลการเปรียบเทียบกับ target |
|---|---|---|---|---|---|
| 1 | 1 | 18 | 9 | 58 | น้อยกว่า |
| 2 | 10 | 18 | 14 | 84 | มากกว่า |
| 3 | 10 | 13 | 11 | 61 | น้อยกว่า |
| 4 | 12 | 13 | 12 | 62 | เท่ากับ |
