ការស្វែងរកបែបលោត

ក្បួនដោះស្រាយការស្វែងរកសម្រាប់អារេដែលបានតម្រៀប។ គំនិតជាមូលដ្ឋានគឺពិនិត្យធាតុតិចជាងមុនដោយលោតទៅមុខតាមជំហានថេរ។

Visualization

Step 1 / 10

Speed:

Details

Analogy

ลองนึกภาพการหาหน้าในหนังสือ แทนที่จะพลิกทีละหน้า (การค้นหาเชิงเส้น) คุณจะกระโดดไปข้างหน้าเป็นบทๆ เมื่อคุณกระโดดผ่านหน้าที่คุณกำลังมองหา คุณจะกลับไปยังบทก่อนหน้าและพลิกหน้าทีละหน้าเพื่อค้นหา។

Purpose

เพื่อค้นหาเป้าหมายในอาร์เรย์ที่เรียงลำดับโดยการกระโดดไปข้างหน้าเป็นบล็อก แล้วทำการค้นหาเชิงเส้นในบล็อกที่ระบุ เป็นการประนีประนอมระหว่างการค้นหาเชิงเส้นและไบนารี។

Use Cases

ดีกว่าการค้นหาเชิงเส้น แต่ไม่ดีเท่าการค้นหาไบนารี สามารถมีประโยชน์ในระบบที่การกระโดดกลับมีค่าใช้จ่ายสูง។

Algorithm Steps

Line 1

step = sqrt(n)

prev = 0

while arr[min(step, n)-1] < target:

prev = step

step += sqrt(n)

if prev >= n: return -1

while arr[prev] < target:

prev++

if prev == min(step, n): return -1

if arr[prev] == target: return prev

return -1

Current

Executed

Pending

Explanation

What's Happening?

Step 1/10

ស្វែងរកเป้าหมาย 55។ ប្រវែងអារេគឺ 12 ដូច្នេះជំហានលោតគឺ sqrt(12) ≈ 3។

Updates with each step • Clickfor full view

Code Implementation

import math

def jump_search(arr, target):
    n = len(arr)
    step = int(math.sqrt(n))
    prev = 0
    while arr[min(step, n) - 1] < target:
        prev = step
        step += int(math.sqrt(n))
        if prev >= n:
            return -1
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1
    if arr[prev] == target:
        return prev
    return -1

ការស្វែងរកបែបលោត - Interactive Visualization | AlgoViz | AlgoViz

ការស្វែងរក​បែប​លោត