برنامه پیدا کردن k نزدیک ترین عنصر به یک مقدار — راهنمای کاربردی

در این مطلب، روش نوشتن برنامه پیدا کردن k نزدیک ترین عنصر به یک مقدار خاص داده شده در ورودی، آموزش داده شده است. یک آرایه مرتب شده arr[]‎ و مقدار X موجود است. هدف پیدا کردن k عنصر نزدیک به مقدار X در آرایه arr[]‎ است. مثال‌های زیر در این رابطه قابل توجه هستند. شایان ذکر است، پیاده‌سازی روش آموزش داده شده در این مطلب، در زبان‌های برنامه‌نویسی گوناگون شامل «سی‌پلاس‌پلاس» (++C)، «سی» (C)، «جاوا» (Java)، «پایتون ۳» (Python 3) و «پی‌اچ‌پی» (PHP) انجام شده است.

Input: K = 4, X = 35
arr[] = {12, 16, 22, 30, 35, 39, 42, 
45, 48, 50, 53, 55, 56}
Output: 30 39 42 45

شایان توجه است که اگر خود عنصر X در آرایه وجود داشته باشد، نباید در خروجی ارائه شود. در واقع، تنها نزدیک‌ترین عناصر به X هستند که باید در خروجی بازگردانده شوند. در راهکارهای زیر، فرض می‌شود همه عناصر اولیه از یکدیگر متمایز هستند. یک راهکار ساده، انجام جستجوی خطی برای k نزدیک‌ترین عنصر است.

جستجوی خطی برای پیدا کردن k نزدیک ترین عنصر به یک مقدار

1. کار را از اولین عنصر آغاز کن و جستجو را برای «نقطه هم‌گذری» (Crossover Point) (نقطه‌ای پیش از X که عناصر کوچک‌تر یا مساوی X باشند و همچنین، نقطه‌ای پس از X که در آن عناصر بزرگ‌تر از X هستند) انجام بده. این گام از مرتبه O(n)‎ است.
2. هنگامی که نقطه هم‌گذری پیدا شد، می‌توان عناصر را در دو سمت نقطه هم‌گذری برای چاپ کردن k نزدیک‌ترین عنصر مقایسه کرد. این گام از درجه O(k)‎ است.

جستجوی دودویی برای پیدا کردن k نزدیک ترین عنصر به یک مقدار

پیچیدگی زمانی راهکار بالا (جستجوی خطی) از درجه O(n)‎ است. یک راهکار بهینه، پیدا کردن k عنصر در زمان O(Logn + k)‎ است. برای رسیدن به زمان بیان شده، یک ایده استفاده از «جستجوی دودویی» (Binary Search) برای پیدا کردن نقطه هم‌گذری است. هنگامی که اندیس نقطه هم‌گذری پیدا شد، می‌توان k نزدیک‌ترین عنصر را در زمان O(k)‎ پیدا کرد.

پیدا کردن k نزدیک ترین عنصر به یک مقدار در C/C++‎ با جستجوی دودویی

#include<stdio.h> 
  
/* Function to find the cross over point (the point before 
   which elements are smaller than or equal to x and after 
   which greater than x)*/
int findCrossOver(int arr[], int low, int high, int x) 
{ 
  // Base cases 
  if (arr[high] <= x) // x is greater than all 
    return high; 
  if (arr[low] > x)  // x is smaller than all 
    return low; 
  
  // Find the middle point 
  int mid = (low + high)/2;  /* low + (high - low)/2 */
  
  /* If x is same as middle element, then return mid */
  if (arr[mid] <= x && arr[mid+1] > x) 
    return mid; 
  
  /* If x is greater than arr[mid], then either arr[mid + 1] 
    is ceiling of x or ceiling lies in arr[mid+1...high] */
  if(arr[mid] < x) 
      return findCrossOver(arr, mid+1, high, x); 
  
  return findCrossOver(arr, low, mid - 1, x); 
} 
  
// This function prints k closest elements to x in arr[]. 
// n is the number of elements in arr[] 
void printKclosest(int arr[], int x, int k, int n) 
{ 
    // Find the crossover point 
    int l = findCrossOver(arr, 0, n-1, x); 
    int r = l+1;   // Right index to search 
    int count = 0; // To keep track of count of elements already printed 
  
    // If x is present in arr[], then reduce left index 
    // Assumption: all elements in arr[] are distinct 
    if (arr[l] == x) l--; 
  
    // Compare elements on left and right of crossover 
    // point to find the k closest elements 
    while (l >= 0 && r < n && count < k) 
    { 
        if (x - arr[l] < arr[r] - x) 
            printf("%d ", arr[l--]); 
        else
            printf("%d ", arr[r++]); 
        count++; 
    } 
  
    // If there are no more elements on right side, then 
    // print left elements 
    while (count < k && l >= 0) 
        printf("%d ", arr[l--]), count++; 
  
    // If there are no more elements on left side, then 
    // print right elements 
    while (count < k && r < n) 
        printf("%d ", arr[r++]), count++; 
} 
  
/* Driver program to check above functions */
int main() 
{ 
   int arr[] ={12, 16, 22, 30, 35, 39, 42, 
               45, 48, 50, 53, 55, 56}; 
   int n = sizeof(arr)/sizeof(arr[0]); 
   int x = 35, k = 4; 
   printKclosest(arr, x, 4, n); 
   return 0; 
}

پیدا کردن k نزدیک ترین عنصر به یک مقدار در جاوا با جستجوی دودویی

// Java program to find k closest elements to a given value 
class KClosest 
{ 
    /* Function to find the cross over point (the point before 
       which elements are smaller than or equal to x and after 
       which greater than x)*/
    int findCrossOver(int arr[], int low, int high, int x) 
    { 
        // Base cases 
        if (arr[high] <= x) // x is greater than all 
            return high; 
        if (arr[low] > x)  // x is smaller than all 
            return low; 
  
        // Find the middle point 
        int mid = (low + high)/2;  /* low + (high - low)/2 */
  
        /* If x is same as middle element, then return mid */
        if (arr[mid] <= x && arr[mid+1] > x) 
            return mid; 
  
        /* If x is greater than arr[mid], then either arr[mid + 1] 
          is ceiling of x or ceiling lies in arr[mid+1...high] */
        if(arr[mid] < x) 
            return findCrossOver(arr, mid+1, high, x); 
  
        return findCrossOver(arr, low, mid - 1, x); 
    } 
  
    // This function prints k closest elements to x in arr[]. 
    // n is the number of elements in arr[] 
    void printKclosest(int arr[], int x, int k, int n) 
    { 
        // Find the crossover point 
        int l = findCrossOver(arr, 0, n-1, x);  
        int r = l+1;   // Right index to search 
        int count = 0; // To keep track of count of elements 
                       // already printed 
  
        // If x is present in arr[], then reduce left index 
        // Assumption: all elements in arr[] are distinct 
        if (arr[l] == x) l--; 
  
        // Compare elements on left and right of crossover 
        // point to find the k closest elements 
        while (l >= 0 && r < n && count < k) 
        { 
            if (x - arr[l] < arr[r] - x) 
                System.out.print(arr[l--]+" "); 
            else
                System.out.print(arr[r++]+" "); 
            count++; 
        } 
  
        // If there are no more elements on right side, then 
        // print left elements 
        while (count < k && l >= 0) 
        { 
            System.out.print(arr[l--]+" "); 
            count++; 
        } 
  
  
        // If there are no more elements on left side, then 
        // print right elements 
        while (count < k && r < n) 
        { 
            System.out.print(arr[r++]+" "); 
            count++; 
        } 
    } 
  
    /* Driver program to check above functions */
    public static void main(String args[]) 
    { 
        KClosest ob = new KClosest(); 
        int arr[] = {12, 16, 22, 30, 35, 39, 42, 
                     45, 48, 50, 53, 55, 56
                    }; 
        int n = arr.length; 
        int x = 35, k = 4; 
        ob.printKclosest(arr, x, 4, n); 
    } 
} 
/* This code is contributed by Rajat Mishra */

پیدا کردن k نزدیک ترین عنصر به یک مقدار در پایتون ۳ با جستجوی دودویی

# Function to find the cross over point  
# (the point before which elements are  
# smaller than or equal to x and after  
# which greater than x)  
def findCrossOver(arr, low, high, x) :  
  
    # Base cases  
    if (arr[high] <= x) : # x is greater than all  
        return high 
          
    if (arr[low] > x) : # x is smaller than all  
        return low  
      
    # Find the middle point  
    mid = (low + high) // 2 # low + (high - low)// 2  
      
    # If x is same as middle element,  
    # then return mid  
    if (arr[mid] <= x and arr[mid + 1] > x) : 
        return mid  
      
    # If x is greater than arr[mid], then  
    # either arr[mid + 1] is ceiling of x  
    # or ceiling lies in arr[mid+1...high]  
    if(arr[mid] < x) : 
        return findCrossOver(arr, mid + 1, high, x) 
      
    return findCrossOver(arr, low, mid - 1, x) 
  
# This function prints k closest elements to x  
# in arr[]. n is the number of elements in arr[]  
def printKclosest(arr, x, k, n) : 
      
    # Find the crossover point  
    l = findCrossOver(arr, 0, n - 1, x) 
    r = l + 1 # Right index to search  
    count = 0 # To keep track of count of  
              # elements already printed  
  
    # If x is present in arr[], then reduce  
    # left index. Assumption: all elements  
    # in arr[] are distinct  
    if (arr[l] == x) : 
        l -= 1
  
    # Compare elements on left and right of crossover  
    # point to find the k closest elements  
    while (l >= 0 and r < n and count < k) : 
          
        if (x - arr[l] < arr[r] - x) : 
            print(arr[l], end = " ")  
            l -= 1
        else : 
            print(arr[r], end = " ")  
            r += 1
        count += 1
  
    # If there are no more elements on right  
    # side, then print left elements  
    while (count < k and l >= 0) : 
        print(arr[l], end = " ") 
        l -= 1
        count += 1
  
    # If there are no more elements on left  
    # side, then print right elements  
    while (count < k and r < n) :  
        print(arr[r], end = " ") 
        r += 1
        count += 1
  
# Driver Code 
if __name__ == "__main__" : 
  
    arr =[12, 16, 22, 30, 35, 39, 42,  
              45, 48, 50, 53, 55, 56] 
                  
    n = len(arr) 
    x = 35
    k = 4
      
    printKclosest(arr, x, 4, n) 
      
# This code is contributed by Ryuga

پیدا کردن k نزدیک ترین عنصر به یک مقدار در C#‎ با جستجوی دودویی

// C# program to find k closest elements to 
// a given value 
using System; 
  
class GFG { 
      
    /* Function to find the cross over point  
    (the point before which elements are 
    smaller than or equal to x and after which 
    greater than x)*/
    static int findCrossOver(int []arr, int low, 
                                int high, int x) 
    { 
          
        // Base cases 
        // x is greater than all 
        if (arr[high] <= x) 
            return high; 
              
        // x is smaller than all 
        if (arr[low] > x)  
            return low; 
  
        // Find the middle point 
        /* low + (high - low)/2 */
        int mid = (low + high)/2;  
  
        /* If x is same as middle element, then 
        return mid */
        if (arr[mid] <= x && arr[mid+1] > x) 
            return mid; 
  
        /* If x is greater than arr[mid], then  
        either arr[mid + 1] is ceiling of x or 
        ceiling lies in arr[mid+1...high] */
        if(arr[mid] < x) 
            return findCrossOver(arr, mid+1,  
                                      high, x); 
  
        return findCrossOver(arr, low, mid - 1, x); 
    } 
  
    // This function prints k closest elements  
    // to x in arr[]. n is the number of  
    // elements in arr[] 
    static void printKclosest(int []arr, int x, 
                                  int k, int n) 
    { 
          
        // Find the crossover point 
        int l = findCrossOver(arr, 0, n-1, x);  
          
        // Right index to search 
        int r = l + 1;  
          
        // To keep track of count of elements 
        int count = 0;  
  
        // If x is present in arr[], then reduce  
        // left index Assumption: all elements in 
        // arr[] are distinct 
        if (arr[l] == x) l--; 
  
        // Compare elements on left and right of  
        // crossover point to find the k closest 
        // elements 
        while (l >= 0 && r < n && count < k) 
        { 
            if (x - arr[l] < arr[r] - x) 
                Console.Write(arr[l--]+" "); 
            else
                Console.Write(arr[r++]+" "); 
            count++; 
        } 
  
        // If there are no more elements on right  
        // side, then print left elements 
        while (count < k && l >= 0) 
        { 
            Console.Write(arr[l--]+" "); 
            count++; 
        } 
  
        // If there are no more elements on left  
        // side, then print right elements 
        while (count < k && r < n) 
        { 
            Console.Write(arr[r++] + " "); 
            count++; 
        } 
    } 
  
    /* Driver program to check above functions */
    public static void Main() 
    { 
        int []arr = {12, 16, 22, 30, 35, 39, 42, 
                         45, 48, 50, 53, 55, 56}; 
        int n = arr.Length; 
        int x = 35; 
        printKclosest(arr, x, 4, n); 
    } 
} 
  
// This code is contributed by nitin mittal.

پیدا کردن k نزدیک ترین عنصر به یک مقدار در PHP با جستجوی دودویی

<?php 
// PHP Program to Find k closest  
// elements to a given value 
  
/* Function to find the cross  
   over point (the point before 
   which elements are smaller  
   than or equal to x and after 
   which greater than x) */
function findCrossOver($arr, $low,  
                       $high, $x) 
{ 
      
    // Base cases 
      
    // x is greater than all 
    if ($arr[$high] <= $x)  
        return $high; 
          
    // x is smaller than all 
    if ($arr[$low] > $x)  
        return $low; 
      
    // Find the middle point 
    /* low + (high - low)/2 */
    $mid = ($low + $high)/2;  
      
    /* If x is same as middle  
       element, then return mid */
    if ($arr[$mid] <= $x and
        $arr[$mid + 1] > $x) 
        return $mid; 
      
    /* If x is greater than arr[mid],  
       then either arr[mid + 1] is  
       ceiling of x or ceiling lies  
       in arr[mid+1...high] */
    if($arr[$mid] < $x) 
        return findCrossOver($arr, $mid + 1,  
                                 $high, $x); 
      
    return findCrossOver($arr, $low, 
                      $mid - 1, $x); 
} 
  
// This function prints k 
// closest elements to x in arr[]. 
// n is the number of elements  
// in arr[] 
function printKclosest($arr, $x, $k, $n) 
{ 
      
    // Find the crossover point 
    $l = findCrossOver($arr, 0, $n - 1, $x); 
      
    // Right index to search 
    $r = $l + 1; 
      
    // To keep track of count of 
    // elements already printed 
    $count = 0;  
  
    // If x is present in arr[],  
    // then reduce left index 
    // Assumption: all elements  
    // in arr[] are distinct 
    if ($arr[$l] == $x) $l--; 
  
    // Compare elements on left  
    // and right of crossover 
    // point to find the k  
    // closest elements 
    while ($l >= 0 and $r < $n 
              and $count < $k) 
    { 
        if ($x - $arr[$l] < $arr[$r] - $x) 
            echo $arr[$l--]," "; 
        else
            echo $arr[$r++]," "; 
        $count++; 
    } 
  
    // If there are no more 
    // elements on right side, 
    // then print left elements 
    while ($count < $k and $l >= 0) 
        echo $arr[$l--]," "; $count++; 
  
    // If there are no more  
    // elements on left side,  
    // then print right elements 
    while ($count < $k and $r < $n) 
        echo $arr[$r++]; $count++; 
} 
  
// Driver Code 
$arr =array(12, 16, 22, 30, 35, 39, 42, 
                45, 48, 50, 53, 55, 56); 
$n = count($arr); 
$x = 35; $k = 4; 
  
printKclosest($arr, $x, 4, $n); 
  
// This code is contributed by anuj_67. 
?>

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

39 30 42 45

پیچیدگی زمانی این روش از درجه O(Logn + k)‎ است.

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

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• الگوریتم بازی مار و پله همراه با کد — به زبان ساده
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده
• الگوریتم جست و جوی دودویی در جاوا اسکریپت — به زبان ساده

^^