در این مطلب، روش پیدا کردن k عنصر نزدیک به یک مقدار داده شده است. در این راستا، فرض می‌شود که آرایه مرتب شده arr[]‎ و یک مقدار X داده شده است. هدف پیدا کردن k نزدیک‌ترین عنصر به مقدار X در arr[]‎ است. برای درک بهتر این مسئله، مثال زیر توصیه می‌شود.

Input: K = 4, X = 35
       arr[] = {12, 16, 22, 30, 35, 39, 42, 
               ۴۵, ۴۸, ۵۰, ۵۳, ۵۵, ۵۶}
Output: 30 39 42 45

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

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

پیچدگی زمانی روش بالا از درجه O(n)‎ است.

یک «راهکار بهینه» (Optimized Solution) پیدا کردن عناصر در زمان از درجه 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, 
               ۴۵, ۴۸, ۵۰, ۵۳, ۵۵, ۵۶}; 
   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, 
                     ۴۵, ۴۸, ۵۰, ۵۳, ۵۵, ۵۶
                    }; 
        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,  
              ۴۵, ۴۸, ۵۰, ۵۳, ۵۵, ۵۶] 
                  
    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, 
                         ۴۵, ۴۸, ۵۰, ۵۳, ۵۵, ۵۶}; 
        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, 
                ۴۵, ۴۸, ۵۰, ۵۳, ۵۵, ۵۶); 
$n = count($arr); 
$x = 35; $k = 4; 
  
printKclosest($arr, $x, 4, $n); 
  
// This code is contributed by anuj_67. 
?>

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

۳۹ ۳۰ ۴۲ ۴۵

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

منبع [+]

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

• مجموعه آموزش‌های داده‌کاوی و یادگیری ماشین
• ​آموزش مدیریت فایل‌ها و اسناد با استفاده از ذخیره ابری
• مجموعه آموزش‌‌های هوش مصنوعی
• ابزارهای یادگیری ماشین متن باز — راهنمای کاربردی
• هوش مصنوعی در کسب و کار — بررسی جامع
• کلان داده یا مِه داده (Big Data) — از صفر تا صد