إيجاد أقرب عدد للعدد المعطى في مصفوفة مرتبة

المطلوب في هذه المسألة هو إيجاد أقرب عدد للعدد المعطى في مصفوفة مرتبة من الأعداد الصحيحة التي قد تحتوي على أعداد مكررة أو ذات إشارة سالبة.

مثال:

Input : arr[] = {1, 2, 4, 5, 6, 6, 8, 9}
             Target number = 11
Output : 9
العدد 9 هو أقرب عدد في المصفوفة للعدد 11

Input :arr[] = {2, 5, 6, 7, 8, 8, 9}; 
       Target number = 4
Output : 5

خطوات الخوارزمية

يمكن استخدام الطريقة البسيطة لحل هذه المسألة، وتتمثّل هذه الطريقة في التنقل عبر جميع عناصر المصفوفة ومتابعة القيمة المطلقة للفرق بين العنصر الحالي وجميع العناصر، ثم تُعاد أصغر قيمة مطلقة.

ويمكن حلّ هذه المسألة بكفاءة أكبر باستخدام أسلوب فرِّق تسد وذلك بالاستفادة من خوارزمية البحث الثنائي:

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة:

• C++‎:

#include <iostream> 
using namespace std; 

int getClosest(int, int, int); 

// تعيد الدالة أقرب عدد للعدد المعطى في المصفوفة
int findClosest(int arr[], int n, int target) 
{ 
	// الحالات الأساس 
	if (target <= arr[0]) 
		return arr[0]; 
	if (target >= arr[n - 1]) 
		return arr[n - 1]; 

	// تنفيذ عملية البحث الثنائي
	int i = 0, j = n, mid = 0; 
	while (i < j) { 
		mid = (i + j) / 2; 

		if (arr[mid] == target) 
			return arr[mid]; 

		/* إن كان العدد المطلوب أقل من العدد الموجود في وسط المصفوفة
		يجري البحث في الجانب الأيسر منها */
		if (target < arr[mid]) { 

			// إن كان العدد المطلوب أكبر من العنصر الذي يسبق وسط المصفوفة
			// يعاد أقرب العددين إلى العدد المطلوب
			if (mid > 0 && target > arr[mid - 1]) 
				return getClosest(arr[mid - 1], 
								arr[mid], target); 

			/* تكرار ما سبق على النصف الأيسر */
			j = mid; 
		} 

		// إن كان العنصر المطلوب أكبر من العنصر الوسطي في المصفوفة
		else { 
			if (mid < n - 1 && target < arr[mid + 1]) 
				return getClosest(arr[mid], 
								arr[mid + 1], target); 
			i = mid + 1; 
		} 
	} 

	// قي عنصر واحد فقط بعد عملية البحث
	return arr[mid]; 
} 

// تبحث الدالة عن العدد الأقرب إلى العدد المعطى
// تحسب الدالة الفرق بين العددين والعدد المطلوب
// تفترض الدالة أن العدد الثاني أكبر من العدد الأول
// وأنّ العدد المطلوب موجود بينهما
int getClosest(int val1, int val2, 
			int target) 
{ 
	if (target - val1 >= val2 - target) 
		return val2; 
	else
		return val1; 
} 

// اختبار الدوال السابقة 
int main() 
{ 
	int arr[] = { 1, 2, 4, 5, 6, 6, 8, 9 }; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	int target = 11; 
	cout << (findClosest(arr, n, target)); 
}

• بايثون:

# تعيد الدالة أقرب عدد للعدد المعطى في المصفوفة 
def findClosest(arr, n, target): 

	# الحالات الأساس
	if (target <= arr[0]): 
		return arr[0] 
	if (target >= arr[n - 1]): 
		return arr[n - 1] 

	# تنفيذ عملية البحث الثنائي
	i = 0; j = n; mid = 0
	while (i < j): 
		mid = (i + j) / 2

		if (arr[mid] == target): 
			return arr[mid] 

		# إن كان العدد المطلوب أقل من العدد الموجود في وسط المصفوفة
		# يجري البحث في الجانب الأيسر منها 
		if (target < arr[mid]) : 

			# إن كان العدد المطلوب أكبر من العنصر الذي يسبق وسط المصفوفة
			# يعاد أقرب العددين إلى العدد المطلوب
			if (mid > 0 and target > arr[mid - 1]): 
				return getClosest(arr[mid - 1], arr[mid], target) 

			# تكرار ما سبق على النصف الأيسر 
			j = mid 
		
		# إن كان العنصر المطلوب أكبر من العنصر الوسطي في المصفوفة
		else : 
			if (mid < n - 1 and target < arr[mid + 1]): 
				return getClosest(arr[mid], arr[mid + 1], target) 
				
			i = mid + 1
		
	# بقي عنصر واحد فقط بعد عملية البحث 
	return arr[mid] 


# تبحث الدالة عن العدد الأقرب إلى العدد المعطى
# تحسب الدالة الفرق بين العددين والعدد المطلوب
# تفترض الدالة أن العدد الثاني أكبر من العدد الأول
# وأنّ العدد المطلوب موجود بينهما
def getClosest(val1, val2, target): 

	if (target - val1 >= val2 - target): 
		return val2 
	else: 
		return val1 

# اختبار الدوال السابقة
arr = [1, 2, 4, 5, 6, 6, 8, 9] 
n = len(arr) 
target = 11
print(findClosest(arr, n, target))

• جافا:

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class FindClosestNumber { 
	
	// يعيد التابع أقرب عدد للعدد المعطى في المصفوفة
	public static int findClosest(int arr[], int target) 
	{ 
		int n = arr.length; 

		// الحالات الأساس
		if (target <= arr[0]) 
			return arr[0]; 
		if (target >= arr[n - 1]) 
			return arr[n - 1]; 

		// تنفيذ عملية البحث الثنائي 
		int i = 0, j = n, mid = 0; 
		while (i < j) { 
			mid = (i + j) / 2; 

			if (arr[mid] == target) 
				return arr[mid]; 

			/* إن كان العدد المطلوب أقل من العدد الموجود في وسط المصفوفة
			يجري البحث في الجانب الأيسر منها */
			if (target < arr[mid]) { 
		
				// إن كان العدد المطلوب أكبر من العنصر الذي يسبق وسط المصفوفة
				// يعاد أقرب العددين إلى العدد المطلوب
				if (mid > 0 && target > arr[mid - 1]) 
					return getClosest(arr[mid - 1], 
								arr[mid], target); 
				
				/* تكرار ما سبق على النصف الأيسر */
				j = mid;			 
			} 

			// إن كان العنصر المطلوب أكبر من العنصر الوسطي في المصفوفة 
			else { 
				if (mid < n-1 && target < arr[mid + 1]) 
					return getClosest(arr[mid], 
						arr[mid + 1], target);				 
				i = mid + 1;
			} 
		} 

		// بقي عنصر واحد فقط بعد عملية البحث
		return arr[mid]; 
	} 

	// تبحث الدالة عن العدد الأقرب إلى العدد المعطى
    // تحسب الدالة الفرق بين العددين والعدد المطلوب
    // تفترض الدالة أن العدد الثاني أكبر من العدد الأول
    // وأنّ العدد المطلوب موجود بينهما
	public static int getClosest(int val1, int val2, 
										int target) 
	{ 
		if (target - val1 >= val2 - target) 
			return val2;		 
		else
			return val1;		 
	} 

	// اختبار التوابع السابقة
	public static void main(String[] args) 
	{ 
		int arr[] = { 1, 2, 4, 5, 6, 6, 8, 9 }; 
		int target = 11; 
		System.out.println(findClosest(arr, target)); 
	} 
}

تعطي الشيفرات السابقة المخرجات التالية:

9

مصادر

• صفحة Find closest number in array في توثيق الخوارزميات في موقع GeeksforGeeks.