ការស្វែងរកបែបអន្តរបូលណេសិន

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

Visualization

Step 1 / 3

Speed:

Details

Analogy

ស្រមៃថាស្វែងរកឈ្មោះក្នុងសៀវភៅទូរស័ព្ទ។ ប្រសិនបើអ្នកស្វែងរក 'Smith' អ្នកមិនបើកទំព័រកណ្តាលទេ។ ជំនួសមក អ្នកប្រាក់តម្លៃថា 'S' នៅប្រហែល 3/4 នៃសៀវភៅ ហើយបើកទីនោះ។ ការស្វែងរកអន្តរបូលណេសិនធ្វើដូចគ្នា - វាគណនាទីតាំងដែលតម្លៃគោលដៅគួរតែនៅដោយផ្អែកលើតម្លៃនៅព្រំដែន។

Purpose

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

Use Cases

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

Algorithm Steps

Line 1

function interpolationSearch(array, target):

low = 0, high = length(array) - 1

while low <= high and target >= array[low] and target <= array[high]:

if low == high:

if array[low] == target: return low

return -1

pos = low + ((target - array[low]) * (high - low)) / (array[high] - array[low])

if array[pos] == target:

return pos

if array[pos] < target:

low = pos + 1

else:

high = pos - 1

return -1

Current

Executed

Pending

Explanation

What's Happening?

Step 1/3

អារេដែលបានតម្រៀបដំបូង: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]។ ចាប់ផ្តើមការស្វែងរកអន្តរបូលណេសិនដោយ low = 0 និង high = 9។

Updates with each step • Clickfor full view

Code Implementation

def interpolation_search(arr, target):
    low, high = 0, len(arr) - 1
    
    while low <= high and target >= arr[low] and target <= arr[high]:
        if low == high:
            if arr[low] == target:
                return low
            return -1
        
        pos = low + int(((target - arr[low]) * (high - low)) / (arr[high] - arr[low]))
        
        if arr[pos] == target:
            return pos
        if arr[pos] < target:
            low = pos + 1
        else:
            high = pos - 1
    
    return -1