การค้นหาแบบไบนารีเป็นหนึ่งในวิธีที่ง่ายที่สุดในการค้นหาองค์ประกอบในอาร์เรย์
ค่อนข้างบ่อย, โปรแกรมเมอร์, แม้แต่ผู้เริ่มต้น,ใบหน้าที่มีชุดของตัวเลขที่มีความจำเป็นที่จะหาจำนวนหนึ่ง คอลเลกชันนี้เรียกว่าอาร์เรย์ และเพื่อหาองค์ประกอบที่ถูกต้องในนั้นมีหลายวิธี แต่ที่ง่ายที่สุดในหมู่พวกเขาโดยทางด้านขวาสามารถได้รับการพิจารณาการค้นหาแบบไบนารี วิธีคืออะไร? และวิธีการใช้การค้นหาแบบไบนารี? Pascal เป็นสื่อที่ง่ายที่สุดสำหรับการจัดโปรแกรมดังกล่าวดังนั้นเราจึงจะใช้เพื่อการศึกษา
ก่อนอื่นเราจะวิเคราะห์สิ่งที่ข้อดีของวิธีการนี้คือหลังจากทั้งหมดเพื่อให้เราสามารถเข้าใจ,
ดังนั้นหลักการทำงานของสิ่งนี้คืออะไรวิธี? เป็นมูลค่าการกล่าวขวัญที่ค้นหาไบนารีไม่ทำงานในอาร์เรย์ใด ๆ แต่เฉพาะในชุดเรียงลำดับของตัวเลข ในแต่ละขั้นตอนถัดไปองค์ประกอบกลางของอาร์เรย์ (หมายถึงหมายเลของค์ประกอบ) จะถูกนำมา หากจำนวนที่ต้องการสูงกว่าค่าเฉลี่ยทุกอย่างที่อยู่ด้านซ้ายนั่นคือน้อยกว่าองค์ประกอบเฉลี่ยสามารถทิ้งและไม่ได้ค้นหาที่นั่น ในทางตรงกันข้ามถ้าน้อยกว่าค่าเฉลี่ยในหมู่ตัวเลขทางด้านขวาคุณจะไม่สามารถมองหาได้ ต่อไปเราจะเลือกพื้นที่การค้นหาใหม่ซึ่งองค์ประกอบส่วนกลางของอาร์เรย์ทั้งหมดจะเป็นองค์ประกอบแรกและส่วนสุดท้ายจะยังคงเป็นส่วนสุดท้าย จำนวนเฉลี่ยของพื้นที่ใหม่จะเป็น¼ของกลุ่มทั้งหมดนั่นคือ (องค์ประกอบสุดท้าย + องค์ประกอบเฉลี่ยของอาร์เรย์ทั้งหมด) / 2 อีกครั้งการดำเนินการเดียวกันจะดำเนินการ - เปรียบเทียบกับจำนวนเฉลี่ยของอาร์เรย์ ถ้าค่าที่ต้องการน้อยกว่าค่าเฉลี่ยให้ละทิ้งด้านขวามือและทำแบบเดิมจนกว่าจะพบองค์ประกอบส่วนกลางนี้
แน่นอนดีที่สุดคือดูตัวอย่างการค้นหาไบนารีที่เขียนขึ้น Pascal นี่เหมาะสำหรับทุกคน - รุ่นไม่สำคัญ ลองเขียนโปรแกรมง่ายๆ
จะมีอาร์เรย์ตั้งแต่ 1 ถึง h ที่มีชื่อ"massiv" ตัวแปร denoting เขตแดนการค้นหาที่ต่ำกว่าเรียกว่า "niz" ขอบเขตด้านบนที่ชื่อว่า "verh" ส่วนกลางของการค้นหาคือ "sredn"; และหมายเลขที่ต้องการคือ "isk"
ดังนั้นอันดับแรกกำหนดขอบเขตบนและล่างของช่วงการค้นหา:
niz: = 1;
verh: = h + 1;
จากนั้นเราจะจัดวงจร "ในขณะที่ด้านล่างมีค่าน้อยกว่าขีด จำกัด บน":
ขณะที่ niz <verh - 1 ทำ
เริ่มต้น
ในแต่ละขั้นตอนแบ่งส่วนโดย 2:
sredn: = (niz + verh) div 2; {ใช้ฟังก์ชัน div เพราะเราแบ่งส่วนที่เหลือ}
ทุกครั้งที่เราทำเช็ค ถ้าค่าเฉลี่ยเท่ากับค่าที่ต้องการให้เราตัดวงจรเนื่องจากองค์ประกอบที่ต้องการได้พบแล้ว:
ถ้า sredn = isk ก็จะแตก;
หากองค์ประกอบเฉลี่ยของอาร์เรย์มากกว่าส่วนที่เรากำลังมองหาให้ทิ้งด้านซ้ายนั่นคือเรากำหนดองค์ประกอบส่วนกลางให้กับขอบเขตด้านบน:
ถ้า massiv [sredn]> isk แล้ว verh: = sredn;
และถ้าในทางตรงกันข้ามเราจะทำให้ขอบเขตล่าง:
อื่น niz: = sredn;
จบ;
นั่นคือทั้งหมดที่จะอยู่ในโปรแกรม
เราจะวิเคราะห์ว่าวิธีไบนารีจะมีลักษณะเป็นอย่างไรในทางปฏิบัติ เราใช้อาร์เรย์ดังกล่าว: 1, 3, 5, 7, 10, 12, 18 และค้นหาตัวเลข 12 ในนั้น
โดยรวมแล้วเรามี 7 องค์ประกอบดังนั้นค่าเฉลี่ยจะเป็นที่สี่ค่าของมัน 7
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
ตั้งแต่ 12 มากกว่า 7 องค์ประกอบ 1,3 และ 5 สามารถทิ้งได้ ต่อไปเรามีเลข 4 ด้านซ้าย 4/2 โดยที่เหลือเป็น 2 ดังนั้นองค์ประกอบกลางใหม่จะเท่ากับ 10
| 7 | 10 | 12 | 18 |
ที่นี่องค์ประกอบกลางมีอยู่แล้ว 12 นี่คือจำนวนที่ต้องการ งานเสร็จสมบูรณ์ - พบหมายเลข 12
