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