ภาษา :
SWEWE สมาชิก :เข้าสู่ระบบ |การลงทะเบียน
ค้นหา
ชุมชนวิกิพีเดีย |คำตอบสารานุกรม |ส่งคำถาม |ความรู้คำศัพท์ |อัปโหลดความรู้
ก่อน 1 ต่อไป เลือกหน้า

ค้นหาแบบไบนารี

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

ขั้นตอนวิธีการต้องใช้

โครงสร้างการจัดเก็บต่อเนื่องจะต้องใช้

2 ต้องสั่งซื้อตามขนาดของคำหลัก

ความซับซ้อนของขั้นตอนวิธี

สมมติว่าอาร์เรย์ของความยาว n, ความซับซ้อนของขั้นตอนวิธีคือ o (log (n))

นี่คือบางส่วนหลอกรหัสเลขฐานสองเพื่อการค้นหา:

BinarySearch (สูงสุด, นาที, DES)

กลาง <(สูงสุด นาที) / 2

ในขณะที่ (นาที <= สูงสุด)

= กลาง (นาที สูงสุด) / 2

ถ้ากลาง = des แล้ว

กลับกลาง

elseif กลาง> des แล้ว

max = กลาง 1-

อื่น

นาที = กลาง 1

กลับสูงสุด

วิธีการค้นหาแบบไบนารีที่เรียกว่าวิธีการค้นหาแบบไบนารีซึ่งใช้ประโยชน์เต็มที่จากความสัมพันธ์ระหว่างองค์ประกอบของคำสั่งที่ใช้ในการแบ่งและพิชิตกลยุทธ์ในกรณีที่เลวร้ายที่สุดเพื่อให้งานค้นหาด้วย O (log n) แนวคิดพื้นฐานคือว่าองค์ประกอบ n เป็นประมาณจำนวนเดียวกันของสองและครึ่งใช้ [n / 2] และต้องการหา x สำหรับการเปรียบเทียบถ้า x = [n / 2] คือการหา x, สิ้นสุดขั้นตอนวิธีการ ถ้า x <[n / 2] แล้วเราเหลือเพียงครึ่งหนึ่งของอาร์เรย์การค้นหาอย่างต่อเนื่องสำหรับ x (นี้อนุมานว่าองค์ประกอบมากมายที่นำเสนอในลำดับจากน้อยไปมาก) ถ้า x> [n / 2] จากนั้นเราก็ยังคงครึ่งขวาของอาร์เรย์ x ค้นหา

วิธีการค้นหาแบบไบนารีทั่วไป BUG มีค่าที่สำคัญที่ไม่ได้เป็นคนสุดท้ายที่จะพบหรือค่าแรก สามารถเปรียบเทียบกับที่ผ่านมาตัวเลขสองซึ่งในท้ายที่สุดอีกครั้งเพื่อกำหนดมูลค่าของค่าเท่ากันและมอง

รหัสตัวอย่าง

รหัสที่มาของปาสกาล

รหัสภาษา C

รหัส Java

เรียนสาธารณะ BinarySearch {/ *** ขั้นตอนวิธีการค้นหาแบบไบนารี ** @ พระราม srcArray อาร์เรย์สั่ง * @ พระราม des หาองค์ประกอบอาร์เรย์ * @ กลับ des ทำเครื่องหมายและไม่สามารถหากลับ -1 * / สาธารณะคง int binarySearch (int [] srcArray , int des) {ต่ำ int = 0; int สูง = srcArray.length-1; ​​ในขณะที่ (ต่ำ <= สูง) {int = กลาง ต่ำ (สูง (ต่ำ) / 2); ถ้า (des == srcArray [กลาง ]) {กลับกลาง;} else if (des <srcArray [กลาง]) {สูง = กลาง - 1;} อื่น {ต่ำ = กลาง 1;}} -1 กลับ;} ประชาชนเป็นโมฆะคงหลัก (String args [] ) {int [] src = ใหม่ int [] {1, 3, 5, 7, 8, 9}; System.out.println (binarySearch (src, 3));}} รหัส AAuto

/ / ค้นหาไบนารี

binSearch ฟังก์ชั่น (t, v) {

var p = # ตัน;

var p2;


ก่อน 1 ต่อไป เลือกหน้า
ผู้ใช้งาน ทบทวน
ยังไม่มีความเห็น
ผมต้องการที่จะแสดงความคิดเห็น [ผู้มาเยือน (3.87.*.*) | เข้าสู่ระบบ ]

ภาษา :
| ตรวจสอบรหัส :


ค้นหา

版权申明 | 隐私权政策 | ลิขสิทธิ์ @2018 โลกความรู้สารานุกรม