Page 38 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 38
15-28 โครงสร้างข้อมูลและข ั้นต อนวิธี
N ≥ 1
N2k ≥ 2K
2K ≤ N
k ≤ log N
จ�ำนวนครั้งในการท �ำซ้�ำ k ไม่เกิน log n ดังน ้ันประสิทธิภาพเชิงเวลาป ระมาณ O(log n)
4.3 กรณีทั่วไป
กรณีน ้ีข ้อมูลท ี่ต้องการค ้นหามีค่าอ ยู่ร ะหว่างต �ำแหน่งแ รกแ ละต�ำแหน่งสุดท้ายในอ าร์เรย์เช่น
ข้อมูลที่ต ้องการค้นหา คือ 15
ข้อมูล 1 7 15 16 23 32 34
การค้นหาลักษณะน้ีจะใช้การเปรียบเทียบวนซ้ําจนกว่าขอบซ้ายมีค่ามากกว่าขอบขวา โดยการวนซ้ํา
N
แต่ละครั้งจะลดจ �ำนวนข้อมูลลงเหลือ 2 ซึ่งการวนซ้ํา จะอยู่ระหว่าง 1 กับ log N โดยเฉลี่ยแล้วประสิทธิภาพ
เชิงเวลาประมาณ O(log n)
5. การน�ำ ข น้ั ตอนวิธีการค้นหาข้อมูลแบบทวภิ าคไปประยุกตใ์ชง้ าน
ปัญหาการหาค่าขอบล่างหรือขอบบนของชุดล�ำดับจากค่าที่ก�ำหนดนั้น เป็นการก�ำหนดช่วงของชุดล�ำดับท่ี
สนใจจากลำ� ดับทม่ี อี ยู่ โดยชว่ งของข้อมูลน้นั ตอ้ งมีค่าตามท่กี ำ� หนดดังภาพท่ี 15.7 ซึ่งแสดงถงึ การหาขอบล่างโดยข้อมูล
ท่ีสนใจต ้องม ีค่ามากกว่าค ่าที่ก �ำหนด x
>= x
x
ภาพท่ี 15.7 ขอบล ่างแ ละช ว่ งของข อ้ มูลจ ากคา่ ทก่ี �ำ หนด x
ตัวอย่างท่ี 15.8 ก�ำหนดให้ข้อมูลประกอบด้วย 5 24 33 43 68 73 90 91 และก�ำหนดให้ค่าท่ีต้องการคือ 69 ให้หา
ค่าต�ำแหน่งของข ้อมูลจากข ้อมูลที่ก �ำหนด โดยค ่าท่ีต �ำแหน่งน้ันมากกว่าหรือเท่ากับ 69
ซึ่งก ารแก้ป ัญหาโจทย์นี้จ ะประยุกต์ใช้ว ิธีการข องส ืบค้นแ บบทวิภาค
ขั้นต อนวิธี LowerBoundSearch มีร ายละเอียดด ังนี้
ข้อมูลเข้าประกอบด้วย
อาร์เรย์ข้อมูลท ี่เรียงล �ำดับไว้แ ล้ว A
จ�ำนวนข ้อมูลทั้งหมด n
ค่าข อบล ่าง x
