การค้นหาแบบทวิภาคอย่างมีเอกรูป

การค้นหาแบบทวิภาคอย่างมีเอกรูป (Uniform binary search) เป็นการค้นหาแบบทวิภาค (binary search) ชนิดหนึ่งซึ่งลดขนาดการทำงานของการค้นหาแบบปกติลง ขั้นตอนวิธีนี้ได้ถูกคิดค้นขึ้นโดย โดนัลด์ คนูธ และได้เขียนแนวคิดและการพิสูจน์ประสิทธิภาพไว้ในหนังสือ The Art of Computer Programming,Volume 3 ลักษณะการทำงานโดยรวมของการค้นหาแบบทวิภาคอย่างมีเอกรูป จะคล้ายๆกับการค้นหาแบบทวิภาคแบบธรรมดา แต่จะต่างกันที่การเลือกจุดพิจารณาว่าจะคิดจากตัวแปร และการที่การค้นหาแบบทวิภาคอย่างมีเอกรูป ได้ทำการคำนวณค่า ที่จะพิจารณาไว้ก่อนค้นหานั้น จะทำให้ความเร็วในการทำงานเพิ่มขึ้นโดยเฉลี่ยประมาณ 17% เทียบกับการค้นหาแบบทวิภาคแบบธรรมดา แต่ประสิทธิภาพเชิงเวลาที่คำนวณได้จะมีค่าเท่ากันกับ ประสิทธิภาพเชิงเวลาของการค้นหาแบบทวิภาพแบบธรรมดา นั่นคือ O(log n) ดังนั้นขั้นตอนวิธีแบบการค้นหาแบบทวิภาคอย่างมีเอกรูป จึงไม่ค่อยได้ถูกนำไปใช้กันมากนัก ทั้งนี้อาจเกิดจากการเขียนโค้ดที่ยุ้งยากกว่า แต่ได้ประสิทธิภาพเชิงเวลาเท่ากับการค้นหาแบบทวิภาพแบบธรรม.

3 ความสัมพันธ์: การค้นหาแบบทวิภาคขั้นตอนวิธีโดนัลด์ คนูธ

การค้นหาแบบทวิภาค

ในสาขาวิทยาการคอมพิวเตอร์ การค้นหาแบบทวิภาค (binary search, half-interval search หรือ bisection search) เป็นขั้นตอนวิธีเพื่อหาตำแหน่งของค่าที่ต้องการ (ข้อมูลนำเข้า หรือ "key") ที่ใช้ในแถวลำดับที่ได้มีการเรียงลำดับข้อมูลแล้ว ขั้นตอนวิธีจะเริ่มจากเปรียบเทียบข้อมูลที่นำเข้ากับข้อมูลที่อยู่ตรงกลางของแถวลำดับ ถ้าข้อมูลมีค่าเท่ากันแสดงว่าพบ "คีย์" ที่ต้องการ อาจจะทำการคืนค่าตำแหน่งหรือในที่นี้คือ ดัชนี (index) กลับไป มิฉะนั้นถ้าค่าของข้อมูลนำเข้าที่ต้องการค้นหามีการน้อยกว่าค่าตรงกลางของแถวลำดับ ก็จะทำขั้นตอนวิธีนี้อีกครั้งแต่เปลี่ยนมาค้นหาในแถวลำดับย่อยของแถวลำดับที่ต้องการค้นหาโดยแถวลำดับย่อยจะมีจุดสิ้นสุดที่ตรงกลางของแถวลำดับหลัก หรือถ้าข้อมูลที่ต้องการค้นหามีค่ามากกว่าแล้วจะค้นหาในแถวลำดับย่อยเช่นกันแต่ย้ายจุดเริ่มต้นมาที่ตรงกลางของแถวลำดับหลัก เมื่อทำไปจนแถวลำดับไม่มีสมาชิกอยู่หรือจุดเริ่มต้นมากกว่าจุดสิ้นสุด แสดงว่าไม่มีสมาชิกในแถวลำดับตัวใดที่มีค่าเท่ากับข้อมูลนำเข้าที่ต้องการค้นหา อาจจะคืนค่าว่า "ไม่พบ" การค้นหาแบบทวิภาคจะแบ่งครึ่งชุดข้อมูลที่ต้องการค้นหา ดังนั้นจึงจัดให้การค้นหาแบบทวิภาคเป็นขั้นตอนวิธีแบ่งแยกและเอาชนะ และขั้นตอนวิธีการค้นห.

ใหม่!!: การค้นหาแบบทวิภาคอย่างมีเอกรูปและการค้นหาแบบทวิภาค · ดูเพิ่มเติม »

ขั้นตอนวิธี

ั้นตอนวิธี หรือ อัลกอริทึม (algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic) โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time), และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้.

ใหม่!!: การค้นหาแบบทวิภาคอย่างมีเอกรูปและขั้นตอนวิธี · ดูเพิ่มเติม »

โดนัลด์ คนูธ

นัลด์ เออร์วิน คนูธ (Donald Ervin Knuth, 10 มกราคม ค.ศ. 1938 - ปัจจุบัน) เป็นนักวิทยาการคอมพิวเตอร์และศาสตราจารย์ที่มหาวิทยาลัยสแตนฟอร์ดและผู้ชนะรางวัลทัวริง (พ.ศ. 2517) และมีผลงานเขียนทางด้านวิทยาการคอมพิวเตอร์ที่ได้รับการยอมรับ อาทิ เช่น The Art of Computer Programming และ Concrete Mathematics และคิดระบบสร้างเอกสาร TeX.

ใหม่!!: การค้นหาแบบทวิภาคอย่างมีเอกรูปและโดนัลด์ คนูธ · ดูเพิ่มเติม »

เปลี่ยนเส้นทางที่นี่:

Uniform binary search

ยูเนี่ยนพีเดียเป็นแผนที่แนวคิดหรือเครือข่ายความหมายจัดเป็นสารานุกรม - dictionary มันให้คำนิยามสั้น ๆ ของแต่ละแนวคิดและความสัมพันธ์ของมัน

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

ข้อมูลทั้งหมดถูกดึงออกจาก วิกิพีเดีย และมีให้บริการภายใต้ใบอนุญาต สัญญาอนุญาตครีเอทีฟคอมมอนส์ แบบแสดงที่มา-อนุญาตแบบเดียวกัน

ยูเนี่ยนพีเดีย ไม่ได้รับการรับรองโดยหรือร่วมกับมูลนิธิวิกิมีเดีย

Google Play Android และโลโก้ของ Google Play เป็นเครื่องหมายการค้าของ Google Inc.

นโยบายความเป็นส่วนตัว