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

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. 

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

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.

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?>