ในวิทยาการคอมพิวเตอร์การค้นหาแบบเลขชี้กำลัง (เรียกอีกอย่างว่าการค้นหาแบบทวีคูณการค้นหาแบบก้าวกระโดดหรือการค้นหาแบบ Struzik ) ^{[ 1 ]}เป็นอัลกอริทึมที่สร้างโดยJon BentleyและAndrew Chi-Chih Yaoในปี 1976 สำหรับการค้นหารายการที่เรียงลำดับแล้ว ไม่จำกัด/อนันต์^{[ 2 ]}มีหลายวิธีในการใช้งาน โดยวิธีที่พบมากที่สุดคือการกำหนดช่วงที่คีย์การค้นหาอยู่ และทำการค้นหาแบบไบนารีภายในช่วงนั้น ซึ่งใช้เวลา โดยที่คือตำแหน่งของคีย์การค้นหาในรายการ หากคีย์การค้นหาอยู่ในรายการ หรือ คือตำแหน่งที่คีย์การค้นหาควรอยู่ หากคีย์การค้นหาไม่อยู่ในรายการ ${\displaystyle O(\log i)}$${\displaystyle i}$

การค้นหาแบบเลขชี้กำลังยังสามารถใช้ในการค้นหาในรายการที่มีขอบเขตได้ การค้นหาแบบเลขชี้กำลังอาจมีประสิทธิภาพเหนือกว่าการค้นหาแบบดั้งเดิมสำหรับรายการที่มีขอบเขต เช่น การค้นหาแบบไบนารี เมื่อองค์ประกอบที่กำลังค้นหาอยู่ใกล้กับส่วนต้นของอาร์เรย์ เนื่องจาก การค้นหาแบบเลขชี้กำลังจะใช้เวลา โดยที่คือดัชนีขององค์ประกอบที่กำลังค้นหาในรายการ ในขณะที่การค้นหาแบบไบนารีจะใช้เวลา โดยที่คือจำนวนองค์ประกอบในรายการ ${\displaystyle O(\log i)}$${\displaystyle i}$${\displaystyle O(\log n)}$${\displaystyle n}$

การค้นหาแบบเลขชี้กำลังช่วยให้สามารถค้นหาค่าอินพุตที่ระบุ (คีย์การค้นหา) ในรายการที่มีการเรียงลำดับและไม่มีขอบเขตได้ อัลกอริทึมประกอบด้วยสองขั้นตอน ขั้นตอนแรกจะกำหนดช่วงที่คีย์การค้นหาจะอยู่หากอยู่ในรายการ ในขั้นตอนที่สอง จะทำการค้นหาแบบไบนารีในช่วงนี้ ในขั้นตอนแรก สมมติว่ารายการมีการเรียงลำดับจากน้อยไปมาก อัลกอริทึมจะมองหาเลขชี้กำลังตัวแรกj ที่ค่า2j ^{มากกว่า}คีย์การค้นหา ค่า^2j นี้ จะกลายเป็นขอบเขตบนสำหรับการค้นหาแบบไบนารี โดยที่เลขชี้กำลังของ 2 ก่อนหน้า 2j ^{- 1}จะเป็นขอบเขตล่างสำหรับการค้นหาแบบไบนารี^{[ 3 ]}

// ส่งคืนตำแหน่งของคีย์ในอาร์เรย์ arr ที่มีความยาว size template < typename T > int exponential_search ( T arr [], int size , T key ) { if ( size == 0 ) { return NOT_FOUND ; }int bound = 1 ; ในขณะที่bound < size และarr [ bound ] < key ) { bound * = 2 ; }return binary_search ( arr , key , bound / 2 , min ( bound , size )); }

ในแต่ละขั้นตอน อัลกอริทึมจะเปรียบเทียบค่าคีย์การค้นหากับค่าคีย์ที่ดัชนีการค้นหาปัจจุบัน หากองค์ประกอบที่ดัชนีปัจจุบันมีค่าน้อยกว่าคีย์การค้นหา อัลกอริทึมจะทำซ้ำ โดยข้ามไปยังดัชนีการค้นหาถัดไปโดยการคูณด้วย 2 แล้วคำนวณกำลังของ 2 ถัดไป^{[ 3 ]}หากองค์ประกอบที่ดัชนีปัจจุบันมีค่ามากกว่าคีย์การค้นหา อัลกอริทึมจะทราบว่าคีย์การค้นหา หากมีอยู่ในรายการ จะอยู่ในช่วงที่เกิดจากดัชนีการค้นหาก่อนหน้า 2 ^{j - 1}และดัชนีการค้นหาปัจจุบัน 2 ^jจากนั้นจะทำการค้นหาแบบไบนารีโดยมีผลลัพธ์เป็นความล้มเหลว หากคีย์การค้นหาไม่อยู่ในรายการ หรือตำแหน่งของคีย์การค้นหาในรายการ

ขั้นตอนแรกของอัลกอริทึมใช้เวลา โดยที่คือดัชนีที่คีย์ค้นหาจะอยู่ในรายการ เนื่องจากในการกำหนดขอบเขตบนสำหรับการค้นหาแบบไบนารี ลูป while จะถูกดำเนินการจำนวนครั้งพอดี เนื่องจากรายการถูกเรียงลำดับแล้ว หลังจากเพิ่มดัชนีค้นหาเป็นสองเท่าจำนวนครั้ง อัลกอริทึมจะอยู่ที่ดัชนีค้นหาที่มากกว่าหรือเท่ากับiเมื่อดังนั้น ขั้นตอนแรกของอัลกอริทึมจึงใช้เวลา ${\displaystyle O(\log i)}$${\displaystyle i}$${\displaystyle \lceil \log(i)\rceil }$${\displaystyle \lceil \log(i)\rceil }$${\displaystyle 2^{\lceil \log(i)\rceil }\geq i}$${\displaystyle O(\log i)}$

ส่วนที่สองของอัลกอริธึมก็ใช้เวลาเช่นกัน เนื่องจากขั้นตอนที่สองเป็นการค้นหาแบบไบนารี จึงใช้เวลาโดยที่คือขนาดของช่วงที่กำลังค้นหา ขนาดของช่วงนี้จะเป็น 2 ^j - 2 ^{j - 1 โดยที่} j = ดังที่เห็นข้างต้นซึ่งหมายความว่าขนาดของช่วงที่กำลังค้นหาคือ 2 ^{log i} - 2 ^{log i - 1} = 2 ^{log i - 1}ดังนั้นเวลาในการทำงานจึงเป็น log (2 ^{log i - 1} ) = log ( i ) - 1 = . ${\displaystyle O(\log i)}$${\displaystyle O(\log n)}$${\displaystyle n}$${\displaystyle \log i}$${\displaystyle O(\log i)}$

ซึ่งทำให้ขั้นตอนวิธีนี้มีเวลาทำงานรวมที่คำนวณได้จากการรวมเวลาทำงานของทั้งสองขั้นตอนเท่ากับ+ = 2 = . ${\displaystyle O(\log i)}$${\displaystyle O(\log i)}$${\displaystyle O(\log i)}$${\displaystyle O(\log i)}$

Bentley และ Yao เสนอรูปแบบต่างๆ สำหรับการค้นหาแบบเลขชี้กำลัง^{[ 2 ]}รูปแบบต่างๆ เหล่านี้ประกอบด้วยการทำการค้นหาแบบไบนารี แทนที่จะเป็นการค้นหาแบบเอกภาค เมื่อกำหนดขอบเขตบนสำหรับการค้นหาแบบไบนารีในขั้นตอนที่สองของอัลกอริทึม ซึ่งจะแบ่งขั้นตอนแรกของอัลกอริทึมออกเป็นสองส่วน ทำให้อัลกอริทึมโดยรวมเป็นอัลกอริทึมสามขั้นตอน ขั้นตอนแรกใหม่จะกำหนดค่าเช่นเดียวกับก่อนหน้านี้ โดยที่มีค่ามากกว่าคีย์การค้นหาและมีค่าน้อยกว่าคีย์การค้นหา ก่อนหน้านี้ถูกกำหนดในลักษณะเอกภาคโดยการคำนวณกำลังถัดไปของ 2 (เช่น การเพิ่ม 1 ให้กับj ) ในรูปแบบใหม่นี้ เสนอให้คูณสองแทน (เช่น กระโดดจาก 2 ²ไปยัง 2 ⁴แทนที่จะเป็น 2 ³ ) ค่าแรกที่มีค่ามากกว่าคีย์การค้นหาจะสร้างขอบเขตบนที่หยาบกว่าเดิมมาก เมื่อพบแล้ว อัลกอริทึมจะย้ายไปยังขั้นตอนที่สองและทำการค้นหาแบบไบนารีในช่วงที่สร้างขึ้นโดยและ ซึ่งให้เลขชี้กำลัง jขอบเขตบนที่แม่นยำยิ่งขึ้น จากตรงนี้ ขั้นตอนที่สามของอัลกอริธึมจะทำการค้นหาแบบไบนารีในช่วง 2j ^{- 1}และ^2jเช่นเดียวกับก่อนหน้านี้ ประสิทธิภาพของการเปลี่ยนแปลงนี้คือ ${\displaystyle j'}$${\displaystyle 2^{j'}}$${\displaystyle 2^{j'/2}}$${\displaystyle j'}$${\displaystyle j'}$${\displaystyle j'}$${\displaystyle 2^{j'}}$${\displaystyle j'}$${\displaystyle j'/2}$${\displaystyle j'}$${\displaystyle \lfloor \log i\rfloor +2\lfloor \log(\lfloor \log i\rfloor +1)\rfloor +1=O(\log i)}$

เบนท์ลีย์และเหยาได้ขยายรูปแบบนี้ให้เป็นรูปแบบที่ทำการค้นหาแบบไบนารีจำนวนk ครั้งใดๆ ก็ได้ ในขั้นตอนแรกของอัลกอริทึม ทำให้ได้ รูปแบบการค้นหาแบบไบนารีซ้อน kครั้ง เวลาในการทำงานเชิงอะซิมโทติกไม่เปลี่ยนแปลงสำหรับรูปแบบต่างๆ โดยใช้เวลาเท่ากับอัลกอริทึมการค้นหาแบบเอกซ์โปเนนเชียลแบบดั้งเดิม ${\displaystyle O(\log i)}$

นอกจากนี้ โครงสร้างข้อมูลที่มีคุณสมบัตินิ้วแบบไดนามิก เวอร์ชันกระชับ สามารถให้ได้เมื่อใช้ผลลัพธ์ข้างต้นของการค้นหาไบนารีแบบk- ซ้อนบนอาร์เรย์ที่เรียงลำดับ ^{[ 4 ]}ด้วยวิธีนี้ จำนวนการเปรียบเทียบที่ทำระหว่างการค้นหาคือ log ( d ) + log log ( d ) + ... + O (log  ^* d ) โดยที่dคือความแตกต่างในอันดับระหว่างองค์ประกอบสุดท้ายที่เข้าถึงและองค์ประกอบปัจจุบันที่กำลังเข้าถึง

อัลกอริทึมที่ใช้การเพิ่มแบนด์การค้นหาแบบเลขชี้กำลังจะแก้ปัญหาการจัดเรียงคู่ทั่วโลกสำหรับโดยที่คือความยาวของลำดับ และคือระยะทางแก้ไขระหว่างลำดับเหล่านั้น^{[ 5 ] [ 6 ]}${\displaystyle O(ns)}$${\displaystyle n}$${\displaystyle s}$

• การค้นหาเชิงเส้น
• การค้นหาแบบไบนารี
• การค้นหาการแทรกสอด
• การค้นหาแบบไตรภาค
• ตารางแฮช