جستجوی درون یابی (Interpolation Search) — به زبان ساده

۴۸۹ بازدید
آخرین به‌روزرسانی: ۱۹ اردیبهشت ۱۴۰۲
زمان مطالعه: ۷ دقیقه
جستجوی درون یابی (Interpolation Search) — به زبان ساده

در این مطلب، روش انجام «جستجوی درون یابی» (Interpolation Search) بیان و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل  ++C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) انجام شده است. یک آرایه مرتب شده []arr از مقادیر دارای توزیع یکنواخت داده شده است. هدف نوشتن برنامه‌ای است که عنصر مشخص x را در آرایه جستجو کند.

مقدمه‌ای بر جستجوی درون‌یابی

«جستجوی خطی» (Linear Search) عناصر را در زمان O(n)‎، «جستجوی پرشی» (Jump Search) در زمان O(√ n)‎ و «جستجوی دودویی» (Binary Search) در زمان O(Log n)‎ جستجو می‌کند. جستجوی درون یابی نسخه بهبود یافته جستجوی دودویی برای نمونه‌ها است که در آن‌ها مقادیر در آرایه مرتب شده به طور یکنواخت توزیع شده‌اند.

جستجوی دودویی همیشه به عنصر میانی می‌رود تا بررسی کند. در حالی که، جستجوی درون یابی مطابق با مقدار کلید به موقعیت‌های مختلف جستجو می‌رود و آن‌ها را جستجو می‌کند. برای مثال، اگر کلید به آخرین مقدار نزدیک‌تر باشد، جستجوی درون‌یابی احتمال دارد تا جستجو را از سمت انتهایی انجام دهد. برای پیدا کردن موقعیت جهت انجام جستجو، از رابطه زیر استفاده می‌شود.

// The idea of formula is to return higher value of pos
// when element to be searched is closer to arr[hi]. And
// smaller value when closer to arr[lo]
pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-arr[Lo]) ]

arr[] ==> Array where elements need to be searched
x     ==> Element to be searched
lo    ==> Starting index in arr[]
hi    ==> Ending index in arr[]

الگوریتم جستجوی درون یابی

در ادامه، کلیت الگوریتم جستجوی درون یابی توضیح داده شده است.

  • گام ۱: در حلقه، مقدار «pos» را با استفاده از فرمول موقعیت کاوشگر محاسبه می‌کند.
  • گام ۲: اگر مقدار موجود در آن اندیس با مقدار x تطبیق پیدا کرد، اندیس عنصر را بازگردان و خارج بشو.
  • گام ۳: اگر عنصر کمتر از arr[pos]‎ است، موقعیت کاوشگر را از زیر آرایه سمت چپ پیدا کن. در غیر این صورت، در زیر آرایه سمت راست جستجو کن.
  • گام ۴: تا هنگامی که یک عنصر مطابق پیدا شود یا زیر آرایه به صفر کاهش پیدا کند، کار را تکرار کن.

در ادامه، روش پیاده‌سازی الگوریتم بیان شده ارائه شده است.

جستجوی درون یابی در ++C

1// C++ program to implement interpolation search 
2#include<bits/stdc++.h> 
3using namespace std; 
4  
5// If x is present in arr[0..n-1], then returns 
6// index of it, else returns -1. 
7int interpolationSearch(int arr[], int n, int x) 
8{ 
9    // Find indexes of two corners 
10    int lo = 0, hi = (n - 1); 
11  
12    // Since array is sorted, an element present 
13    // in array must be in range defined by corner 
14    while (lo <= hi && x >= arr[lo] && x <= arr[hi]) 
15    { 
16        if (lo == hi) 
17        { 
18            if (arr[lo] == x) return lo; 
19            return -1; 
20        } 
21        // Probing the position with keeping 
22        // uniform distribution in mind. 
23        int pos = lo + (((double)(hi - lo) / 
24            (arr[hi] - arr[lo])) * (x - arr[lo])); 
25  
26        // Condition of target found 
27        if (arr[pos] == x) 
28            return pos; 
29  
30        // If x is larger, x is in upper part 
31        if (arr[pos] < x) 
32            lo = pos + 1; 
33  
34        // If x is smaller, x is in the lower part 
35        else
36            hi = pos - 1; 
37    } 
38    return -1; 
39} 
40  
41// Driver Code 
42int main() 
43{ 
44    // Array of items on which search will 
45    // be conducted. 
46    int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 
47                 22, 23, 24, 33, 35, 42, 47}; 
48    int n = sizeof(arr)/sizeof(arr[0]); 
49  
50    int x = 18; // Element to be searched 
51    int index = interpolationSearch(arr, n, x); 
52  
53    // If element was found 
54    if (index != -1) 
55        cout << "Element found at index " << index; 
56    else
57        cout << "Element not found."; 
58    return 0; 
59} 
60  
61// This code is contributed by Mukul Singh. 

جستجوی درون یابی در C

1// C program to implement interpolation search 
2#include<stdio.h> 
3  
4// If x is present in arr[0..n-1], then returns 
5// index of it, else returns -1. 
6int interpolationSearch(int arr[], int n, int x) 
7{ 
8    // Find indexes of two corners 
9    int lo = 0, hi = (n - 1); 
10  
11    // Since array is sorted, an element present 
12    // in array must be in range defined by corner 
13    while (lo <= hi && x >= arr[lo] && x <= arr[hi]) 
14    { 
15        if (lo == hi){ 
16            if (arr[lo] == x) return lo; 
17            return -1; 
18        } 
19        // Probing the position with keeping 
20        // uniform distribution in mind. 
21        int pos = lo + (((double)(hi-lo) / 
22              (arr[hi]-arr[lo]))*(x - arr[lo])); 
23  
24        // Condition of target found 
25        if (arr[pos] == x) 
26            return pos; 
27  
28        // If x is larger, x is in upper part 
29        if (arr[pos] < x) 
30            lo = pos + 1; 
31  
32        // If x is smaller, x is in the lower part 
33        else
34            hi = pos - 1; 
35    } 
36    return -1; 
37} 
38  
39// Driver Code 
40int main() 
41{ 
42    // Array of items on which search will 
43    // be conducted. 
44    int arr[] =  {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 
45                  24, 33, 35, 42, 47}; 
46    int n = sizeof(arr)/sizeof(arr[0]); 
47  
48    int x = 18; // Element to be searched 
49    int index = interpolationSearch(arr, n, x); 
50  
51    // If element was found 
52    if (index != -1) 
53        printf("Element found at index %d", index); 
54    else
55        printf("Element not found."); 
56    return 0; 
57}

جستجوی درون یابی در جاوا

1// Java program to implement interpolation search 
2  
3class Test 
4{ 
5    // Array of items on which search will 
6    // be conducted. 
7    static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 
8                                         24, 33, 35, 42, 47}; 
9      
10    // If x is present in arr[0..n-1], then returns 
11    // index of it, else returns -1. 
12    static int interpolationSearch(int x) 
13    { 
14        // Find indexes of two corners 
15        int lo = 0, hi = (arr.length - 1); 
16       
17        // Since array is sorted, an element present 
18        // in array must be in range defined by corner 
19        while (lo <= hi && x >= arr[lo] && x <= arr[hi]) 
20        {         
21  
22            if (lo == hi) 
23            { 
24                if (arr[lo] == x) return lo; 
25                return -1; 
26            } 
27         
28            // Probing the position with keeping 
29            // uniform distribution in mind. 
30              
31            int pos = lo + (((hi-lo) / 
32                  (arr[hi]-arr[lo]))*(x - arr[lo])); 
33       
34            // Condition of target found 
35            if (arr[pos] == x) 
36                return pos; 
37       
38            // If x is larger, x is in upper part 
39            if (arr[pos] < x) 
40                lo = pos + 1; 
41       
42            // If x is smaller, x is in the lower part 
43            else
44                hi = pos - 1; 
45        } 
46        return -1; 
47    } 
48    
49    // Driver method  
50    public static void main(String[] args)  
51    { 
52         int x = 18; // Element to be searched 
53         int index = interpolationSearch(x); 
54           
55         // If element was found 
56         if (index != -1) 
57               System.out.println("Element found at index " + index); 
58            else
59               System.out.println("Element not found."); 
60    } 
61}

جستجوی درون یابی در پایتون

1# Python program to implement interpolation search 
2  
3# If x is present in arr[0..n-1], then returns 
4# index of it, else returns -1 
5def interpolationSearch(arr, n, x): 
6    # Find indexs of two corners 
7    lo = 0
8    hi = (n - 1) 
9   
10    # Since array is sorted, an element present 
11    # in array must be in range defined by corner 
12    while lo <= hi and x >= arr[lo] and x <= arr[hi]: 
13        if lo == hi: 
14            if arr[lo] == x:  
15                return lo; 
16            return -1; 
17          
18        # Probing the position with keeping 
19        # uniform distribution in mind. 
20        pos  = lo + int(((float(hi - lo) / 
21            ( arr[hi] - arr[lo])) * ( x - arr[lo]))) 
22  
23        # Condition of target found 
24        if arr[pos] == x: 
25            return pos 
26   
27        # If x is larger, x is in upper part 
28        if arr[pos] < x: 
29            lo = pos + 1; 
30   
31        # If x is smaller, x is in lower part 
32        else: 
33            hi = pos - 1; 
34      
35    return -1
36  
37# Driver Code 
38# Array of items oin which search will be conducted 
39arr = [10, 12, 13, 16, 18, 19, 20, 21, \ 
40                22, 23, 24, 33, 35, 42, 47] 
41n = len(arr) 
42  
43x = 18 # Element to be searched 
44index = interpolationSearch(arr, n, x) 
45  
46if index != -1: 
47    print "Element found at index",index 
48else: 
49    print "Element not found"
50  
51# This code is contributed by Harshit Agrawal

جستجوی درون یابی در #C

1// C# program to implement  
2// interpolation search 
3using System; 
4  
5class GFG 
6{ 
7    // Array of items on which  
8    // search will be conducted. 
9    static int []arr = new int[]{10, 12, 13, 16, 18,  
10                                 19, 20, 21, 22, 23,  
11                                 24, 33, 35, 42, 47}; 
12      
13    // If x is present in  
14    // arr[0..n-1], then  
15    // returns index of it,  
16    // else returns -1. 
17    static int interpolationSearch(int x) 
18    { 
19        // Find indexes of 
20        // two corners 
21        int lo = 0, hi = (arr.Length - 1); 
22      
23        // Since array is sorted,  
24        // an element present in 
25        // array must be in range 
26        // defined by corner 
27        while (lo <= hi &&  
28                x >= arr[lo] &&  
29                x <= arr[hi]) 
30        { 
31            if (lo == hi) 
32            { 
33                if (arr[lo] == x) return lo; 
34                return -1; 
35            } 
36  
37            // Probing the position  
38            // with keeping uniform  
39            // distribution in mind. 
40            int pos = lo + (((hi - lo) /  
41                             (arr[hi] - arr[lo])) *  
42                                   (x - arr[lo])); 
43      
44            // Condition of  
45            // target found 
46            if (arr[pos] == x) 
47                return pos; 
48      
49            // If x is larger, x 
50            // is in upper part 
51            if (arr[pos] < x) 
52                lo = pos + 1; 
53      
54            // If x is smaller, x  
55            // is in the lower part 
56            else
57                hi = pos - 1; 
58        } 
59        return -1; 
60    } 
61  
62    // Driver Code  
63    public static void Main()  
64    { 
65        int x = 18; // Element to be searched 
66        int index = interpolationSearch(x); 
67          
68        // If element was found 
69        if (index != -1) 
70            Console.WriteLine("Element found " + 
71                                   "at index " +  
72                                         index); 
73            else
74            Console.WriteLine("Element not found."); 
75    } 
76} 
77  
78// This code is contributed by anuj_67.

جستجوی درون یابی در PHP

1<?php 
2// PHP program to implement interpolation search 
3  
4// If x is present in arr[0..n-1], then returns  
5// index of it, else returns -1.  
6function interpolationSearch($arr, $x, $n) 
7{ 
8    // Find indexes of two corners 
9    $l = 0; $h = $n - 1; 
10      
11    // Since array is sorted, an element present 
12    // in array must be in range defined by corner 
13    while ($l <= $h and $x >= $arr[$l] and
14                        $x <= $arr[$h]) 
15    { 
16        if ($l == $h) 
17        { 
18              if ($arr[$l] == $x) return $l; 
19              return -1; 
20        } 
21  
22        // Probing the position with keeping 
23        // uniform distribution in mind. 
24        $m = intval($l + (($x - $arr[$l]) * ($h - $l) /  
25                               ($arr[$h] - $arr[$l]))); 
26          
27        // Condition of target found 
28        if ($arr[$m] == $x)  
29        { 
30            return $m; 
31        } 
32          
33        // If x is larger, x is in upper part 
34        elseif ($arr[$m] < $x) 
35        { 
36            $l = $m + 1; 
37        }  
38          
39        // If x is smaller, x is in the lower part 
40        else
41        { 
42            $h = $m - 1; 
43        } 
44    } 
45      
46    return -1; 
47} 
48  
49// Driver Code  
50  
51// Array of items on which search 
52// will be conducted.  
53$arr = array(10, 12, 13, 16, 18, 19, 20, 21,  
54             22, 23, 24, 33, 35, 42, 47);  
55$n = count($arr);  
56$x = 18; // Element to be searched  
57$index = interpolationSearch($arr, $x, $n);  
58  
59// If element was found  
60if ($index != -1)  
61    echo "Element found at index " . $index;  
62else
63    echo "Element not found.";  
64  
65// This code is contributed by Deepika Pathak 
66?>

خروجی قطعه کد بالا به صورت زیر است.

Element found at index 4

اگر عناصر به طور یکنواخت توزیع شده باشند، پیچیدگی زمانی از درجه O (log (log n))‎ خواهد بود. در بدترین حالت می‌توان تا درجه O(n)‎ را به خود بگیرد. پیچیدگی فضای کمکی نیز از درجه O(1)‎ است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۰ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
GeeksforGeeks
نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *