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)