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