Exponential Search

เป็นอัลกอริธึมสร้างโดยJon Bentley and Andrew Chi-Chih Yao ในปี 1976 เพื่อค้นหาเรียงลำดับมากมายหรือไม่มีที่สิ้นสุด วิธีการคือ ประกอบด้วยสองขั้นตอน ขั้นตอนแรกกำหนดช่วงที่คีย์การค้นหาจะอยู่ถ้าอยู่ในรายการ ในขั้นตอนที่สองจะมีการค้นหาแบบไบนารีในช่วงนี้ ในขั้นตอนแรกสมมติว่ารายการถูกเรียงลำดับจากน้อยไปมากอัลกอริทึมจะค้นหาเลขยกกำลังแรก i ซึ่งมีค่ามากกว่า 2i มากกว่าคีย์การค้นหา ค่านี้ 2i กลายเป็นขีดจำกัด สำหรับการค้นหาแบบไบนารีด้วยที่ 2, 2i - 1 ซึ่งเป็นขอบเขตล่างสำหรับการค้นหาแบบไบนารี

 การนำ Exponential Search ไปใช้งานในภาษาPython 
ตัวอย่างภาษาไพทอนdef binarySearch( arr, l, r, x):
    if r >= l:
        mid = l + ( r-l ) / 2

        if arr[mid] == x:
            return mid

        if arr[mid] > x:
            return binarySearch(arr, l, 
                                mid - 1, x)

        return binarySearch(arr, mid + 1, r, x)

    return False

def exponentialSearch(arr, x):

    n = len(arr)
    if arr[0] == x:
        return 0

    i = 1
    while i < n and arr[i] <= x:
        i = i * 2

    return binarySearch( arr, i / 2, min(i, n), x)


arr = [1,3,4,5,13,20,25,40,42,44,53]
x = 13
result = exponentialSearch(arr, x)
print (result)

 อ้างอิง 
exponential-search on geeksforgeeks
หมวดหมู่:ขั้นตอนวิธีการค้นหา