Binary Search (การค้นหาแบบแบ่งครึ่ง)
แนะนำใหม่| English | ความหมาย |
|---|---|
| sorted/ˈsɔːtɪd/ | มีการเรียงลำดับแล้ว |
| Binary search/ˈbaɪnəri sɜːtʃ/ | การค้นหาแบบทวิภาค |
| target/ˈtɑːɡɪt/ | เป้าหมาย |
| middle/ˈmɪdl/ | ตรงกลาง |
| comparison/kəmˈpærɪsn/ | การเปรียบเทียบ |
| halves/hɑːvz/ | แบ่งครึ่ง |
| linear search/ˈlɪnɪə sɜːtʃ/ | การค้นหาแบบเชิงเส้น |
ค้นหา fast ใน sorted list
- Binary search (การค้นหาค่ากลาง) เป็นวิธีที่รวดเร็วในการค้นหา target (เป้าหมาย) value ใน sorted (เรียงลำดับแล้ว) list.
- "Sorted" หมายความว่าค่าอยู่ในลำดับ — เล็กสุดไปใหญ่สุด, ตัวอย่างเช่น.
- มันเร็วกว่ามากในการตรวจสอบทุกไอเท็ม.
- แต่มันมีข้อจำกัดที่เข้มงวดเพียงข้อเดียว.
Binary search ต้องการข้อมูล sorted (เรียงลำดับแล้ว). บน unsorted list มันสามารถกระโดดข้าม target และพลาดมันไปได้. ต้อง sort ก่อนเสมอ — หรือใช้การค้นหารูปแบบอื่น.
Binary Search สามารถใช้ได้กับข้อมูลที่:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
บนข้อมูลที่ไม่เรียงลำดับอาจพลาดเป้าหมายได้
ตรวจสอบตรงกลาง แล้วแบ่งครึ่ง
- แนวคิดง่าย: ตรวจสอบ middle element (องค์ประกอบตรงกลาง). แล้ว:
- ถ้า middle เท่ากับ target, คุณพบมันแล้ว;
- ถ้า target เล็กกว่า, ค้นหาเฉพาะ left half (ครึ่งซ้าย);
- ถ้า target ใหญ่กว่า, ค้นหาเฉพาะ right half (ครึ่งขวา).
การค้นหาเชิงเส้นเทียบกับ binary search
แบบไบนารี减半ช่วง在每个步骤
Linear search ตรวจสอบทุกรายการ; Binary search แบ่งลิสต์ที่เรียงลำดับแล้วออกเป็นสองส่วนในการเปรียบเทียบแต่ละครั้ง จึงใช้ขั้นตอนน้อยกว่ามาก
หากเป้าหมายมีค่ามากกว่าองค์ประกอบตรงกลาง Binary Search จะมองหาต่อในส่วน:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
เป้าหมายที่มีค่ามากกว่าต้องอยู่ในครึ่งขวา (ส่วนที่มีค่าสูงกว่า)
การเปรียบเทียบแต่ละครั้งใน Binary Search ______ ส่วนที่เหลือของลิสต์
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การแบ่งครึ่งในแต่ละขั้นตอนคือเหตุผลที่ทำให้มันเร็วมาก
สำหรับการค้นหาแบบแบ่งครึ่ง (binary search) ในรายการที่เรียงลำดับแล้วที่มี 1000 รายการ จะต้องการการตรวจสอบประมาณกี่ครั้ง? (2^10 = 1024)
Difficulty 2/5 · 140 coins + a small bonus on first completion today
เนื่องจาก 2^10 = 1024 ≥ 1000 ใช้การแบ่งครึ่งประมาณ 10 ครั้งก็พอ
ทำไมมันจึงเร็ว如此
- การเปรียบเทียบแต่ละครั้งจะลดทอนส่วนที่เหลือของรายการลงครึ่งหนึ่ง
- สำหรับ 1000 รายการ การค้นหาแบบเชิงเส้นอาจต้องใช้การตรวจสอบสูงสุดถึง 1000 ครั้ง
- การค้นหาแบบทวิภาคใช้เพียงประมาณ 10 ครั้งเท่านั้น เพราะ $2^{10} = 1024$
- รายการยิ่งใหญ่ ความได้เปรียบก็ยิ่งมาก
Binary Search พบ 14 ใน [2,5,8,11,14,17,20] ด้วยจำนวนการเปรียบเทียบกี่ครั้ง?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ตรงกลาง 11 → ไปขวา; ตรงกลาง 17 → ไปซ้าย; ตรงกลาง 14 → พบ: 3 ครั้ง
บนลิสต์ที่เรียงลำดับขนาดใหญ่ Binary Search ต้องการการเปรียบเทียบน้อยกว่า Linear Search มาก
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การแบ่งครึ่งชนะการตรวจสอบทุกรายการทีละตัว
เปรียบเทียบกับการค้นหาแบบเชิงเส้น
- การค้นหาแบบเชิงเส้นจะตรวจสอบองค์ประกอบทีละตัวไปเรื่อยๆ
- การค้นหาแบบทวิภาคเหนือกว่าในรายการที่เรียงลำดับขนาดใหญ่โดยการลดทอนลงครึ่งหนึ่งในแต่ละขั้นตอน
ค้นหา [2, 5, 8, 11, 14, 17, 20] เพื่อหาค่า 14. ค่าตรงกลางคือ 11; 14 > 11 → ค้นหาในครึ่งขวา [14, 17, 20]. ค่าตรงกลางคือ 17; 14 < 17 → ค้นหา [14]. ค่าตรงกลางคือ 14 — พบในเพียง 3 ครั้งของการเปรียบเทียบ การค้นหาแบบเชิงเส้นต้องใช้เวลา 5 ครั้ง
การค้นหาแบบทวิภาค หา เป้าหมาย ใน รายการที่เรียงลำดับแล้ว โดยการตรวจสอบ ค่าตรงกลาง และเก็บเฉพาะครึ่งที่อาจมีเป้าหมายอยู่ Each การเปรียบเทียบ ลดครึ่ง ช่วง范围, ดังนั้น 1000 รายการต้องใช้ ~10 ครั้ง — น้อยกว่ามากของการ ค้นหาแบบเชิงเส้น ที่ใช้ 1000. มันทำงานได้ เฉพาะ กับข้อมูลที่เรียงลำดับแล้วเท่านั้น