ค้นหาแบบทวิภาค - หนึ่งในวิธีที่ง่ายที่สุดในการหาองค์ประกอบในอาร์เรย์

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

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

ดังนั้นสิ่งที่เป็นหลักการทำงานของวิธีการนี้หรือไม่? ทันทีที่มันควรจะบอกว่าค้นหา binary ทำงานไม่ได้อยู่ในอาร์เรย์ใด ๆ แต่เฉพาะในชุดเรียงลำดับของตัวเลข ในขั้นตอนการดำเนินการแต่ละองค์ประกอบกลางของอาร์เรย์ (หมายถึงจำนวนขององค์ประกอบ) หากจำเป็นต้องใช้ จำนวนที่มีค่ามากกว่า ค่าเฉลี่ยแล้วทั้งหมดที่เหลือที่น้อยกว่าเซลล์เฉลี่ยสามารถยกเลิกและไม่ให้ดูมี ตรงกันข้ามถ้าน้อยกว่าค่าเฉลี่ย - หมู่ตัวเลขเหล่านั้นไปทางขวาคุณจะไม่สามารถค้นหา จากนั้นเลือกพื้นที่ค้นหาใหม่ที่องค์ประกอบแรกจะเป็นองค์ประกอบกลางของอาร์เรย์ทั้งหมดและที่ผ่านมาและจะมีอายุการใช้ ค่าเฉลี่ยของจำนวนสาขาใหม่จะ¼ของทุกส่วนที่เป็น (องค์ประกอบสุดท้าย + องค์ประกอบกลางของอาร์เรย์ทั้งหมด) / 2 อีกครั้งการดำเนินการเดียวกันจะดำเนินการ - การเปรียบเทียบกับค่าเฉลี่ยของจำนวนอาร์เรย์ ถ้าค่าเป้าหมายคือน้อยกว่าค่าเฉลี่ยที่เราปฏิเสธด้านขวาและยังต้องทำต่อไปจนตอนนี้องค์ประกอบกลางนี้จะไม่ต้องการ

แน่นอนมันเป็นดีที่สุดในการดูตัวอย่างของวิธีการเขียนค้นหา binary ปาสคาลที่นี่จะเหมาะกับทุกคน - รุ่นไม่สำคัญ ลองเขียนโปรแกรมง่ายๆ

มันเป็นอาร์เรย์ของ 1 ชั่วโมงภายใต้ชื่อ "massiv" ที่เป็นตัวแปรชี้ไปที่ขอบล่างของการค้นหาที่เรียกว่า "Niz" ขีด จำกัด บนเรียกว่า "verh" คำค้นหาเฉลี่ย - "sredn"; และจำนวนที่ต้องการ - "ISK"

ดังนั้นก่อนที่เรากำหนดขีด จำกัด บนและล่างของการค้นหาช่วง:

Niz = 1;
verh = H + 1;

จากนั้นจัดระเบียบรอบ "จนด้านล่างน้อยกว่าขีด จำกัด บน":

ในขณะที่ Niz เริ่มต้น

ในแต่ละขั้นตอนเราแบ่งส่วนที่ 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

ตั้งแต่มากกว่า 12, 7, 1.3 และ 5 องค์ประกอบที่เราสามารถทิ้ง จากนั้นเราได้มีจำนวน 4 4/2 ไม่มีสารตกค้างเป็น 2 ดังนั้นองค์ประกอบใหม่จะเป็นค่าเฉลี่ยของ 10

ตั้งแต่วันที่ 12 มีค่ามากกว่า 10 เราทิ้ง 7. ยังคงอยู่เพียง 10, 12 และ 18

นี่คือองค์ประกอบกลางที่มีอยู่แล้ว 12 มันเป็นจำนวนที่ต้องการ งานนี้จะเสร็จสมบูรณ์ - เลขที่ 12 พบ