Paulturner-Mitchell.com / คอมพิวเตอร์ / การค้นหาไบนารีเป็นหนึ่งในวิธีที่ง่ายที่สุดในการค้นหาองค์ประกอบในอาร์เรย์

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

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

อันดับแรก เราจะวิเคราะห์ว่าวิธีนี้มีข้อดีอย่างไร เพราะวิธีนี้ทำให้เราเข้าใจได้

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

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

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

จะมีอาร์เรย์ตั้งแต่ 1 ถึง h เรียกว่า"massiv" ตัวแปรแสดงถึงขอบเขตล่างของการค้นหาชื่อ "niz" ขอบเขตบนชื่อ "verh" คำค้นหาตรงกลางชื่อ "sredn"; และจำนวนที่ต้องการคือ "isk"

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

นิซ: = 1;
verh: = ชั่วโมง + 1;

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

ในขณะที่ niz <verh - 1 do
เริ่ม

ในแต่ละขั้นตอน เราแบ่งส่วนออกเป็น 2:

sredn: = (niz + verh) div 2; {ใช้ฟังก์ชัน div เพราะเราหารโดยไม่มีเศษ}

ทุกครั้งที่เราตรวจสอบ หากค่าเฉลี่ยเท่ากับค่าที่ต้องการ เราจะขัดจังหวะการวนซ้ำ เนื่องจากพบองค์ประกอบที่ต้องการแล้ว:

іf sredn = isk ให้แตก;

หากองค์ประกอบตรงกลางของอาร์เรย์มีขนาดใหญ่กว่าที่ต้องการ ให้ละทิ้งด้านซ้าย นั่นคือ กำหนดองค์ประกอบตรงกลางเป็นเส้นขอบด้านบน:

ถ้า massiv [sredn]> isk แล้ว verh: = sredn;

และถ้าตรงกันข้าม เราก็ทำให้มันเป็นขอบล่าง:

อื่น ๆ niz: = sredn;
จบ;