ការស្វែងរកបែបអិចស្ប៉ូណង់ស្យែល

ក្បួនដោះស្រាយស្វែងរកដែលពិសេសសមរម្យសម្រាប់អារេគ្មានព្រំដែន ឬគ្មានទីបញ្ចប់។ វារកជួរដែលធាតុគោលដៅមានដោយបង្កើនសន្ទស្សន៍ជាអិចស្ប៉ូណង់ស្យែល រួចធ្វើការស្វែងរកគោលពីរក្នុងជួរនោះ។

Visualization

Step 1 / 10

Speed:

Details

Analogy

ស្រមៃថាស្វែងរកពាក្យក្នុងវចនានុក្រម ប៉ុន្តែអ្នកមិនដឹងថាវាមានប៉ុន្មានទំព័រទេ។ ជំនួសឱ្យពិនិត្យទំព័រម្តងមួយ (លីនេអ៊ែរ) ឬទាយកណ្តាល (គោលពីរ) អ្នកពិនិត្យទំព័រ 1 រួច 2 រួច 4 រួច 8 រួច 16 ទ្វេដងរហូតដល់អស់ជួរ។ ពេលអស់ជួរ អ្នកដឹងថាពាក្យនៅរវាងទីតាំងចុងក្រោយពីរ ហើយអ្នកអាចប្រើការស្វែងរកគោលពីរក្នុងជួរនោះ។

Purpose

ដើម្បីស្វែងរកក្នុងអារេដែលបានតម្រៀបយ៉ាងមានប្រសិទ្ធភាព ជាពិសេសនៅពេលគោលដៅនៅជិតដើម។ វារួមបញ្ចូលគុណសម្បត្តិនៃការស្វែងរកលីនេអ៊ែរសម្រាប់ជួរតូច ជាមួយការស្វែងរកគោលពីរសម្រាប់ជួរធំ ធ្វើឱ្យវាល្អសម្រាប់អារេគ្មានព្រំដែន។

Use Cases

ល្អសម្រាប់ស្វែងរកបញ្ជីគ្មានព្រំដែន ឬគ្មានទីបញ្ចប់ដែលទំហំមិនត្រូវបានដឹង។ មានប្រយោជន៍នៅពេលធាតុគោលដៅទំនងនៅជិតដើមអារេ។ ប្រើជាទូទៅក្នុងប្រព័ន្ធមូលដ្ឋានទិន្នន័យសម្រាប់សំណួរជួរ។ ប្រើក្នុងពិធីការបណ្តាញសម្រាប់ការគណនាអស់ពេល។

Algorithm Steps

Line 1

function exponentialSearch(array, target):

if array[0] == target:

return 0

i = 1

while i < length(array) and array[i] <= target:

i = i * 2

return binarySearch(array, target, i/2, min(i, length-1))

Current

Executed

Pending

Explanation

What's Happening?

Step 1/10

អារេដែលបានតម្រៀបដំបូង: [2, 3, 4, 10, 40, 50, 60, 70, 80, 90]។ ចាប់ផ្តើមការស្វែងរកបែបអិចស្ប៉ូណង់ស្យែលជាមួយជួរ [0, 9]។

Updates with each step • Clickfor full view

Code Implementation

def exponential_search(arr, target):
    if arr[0] == target:
        return 0

    i = 1
    while i < len(arr) and arr[i] <= target:
        i = i * 2

    # Binary search in the range
    left = i // 2
    right = min(i, len(arr) - 1)

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

ការស្វែងរកបែបអិចស្ប៉ូណង់ស្យែល - Interactive Visualization | AlgoViz | AlgoViz