إيجاد الصغرى المحلية في مصفوفة

تعرف الصغرى المحلية Local minima بأنّها النقطة التي تكون أصغر من النقطتين المجاورتين لها أو مساوية لهما.

يمكن تمثيل النقاط بمصفوفة (لتكن arr[0 .. n-1]‎) من الأعداد الصحيحة المميزة.

ويجدر التنبيه إلى الملاحظتين التاليتين:

• قد تحتوي المصفوفة على أكثر من صغرى محلية والمطلوب هو العثور على أي واحدة منها.
• بطبيعة الحال يكفي النظر إلى عنصر مجاور واحد للعناصر الموجودة عند طرفي المصفوفة.

مثال:

Input: arr[] = {9, 6, 3, 14, 5, 7, 4};
Output: Index of local minima is 2

تعرض المخرجات موقع العنصر 3 وذلك لكونه أصغر من العنصرين المجاورين له، ويجدر التنبيه إلى أنّ موقعي العنصرين 5 و4 يمثّلان إجابتين صحيحتين كذلك لانطباق الشرط السابق عليهما.

Input: arr[] = {23, 8, 15, 2, 3};
Output: Index of local minima is 1

Input: arr[] = {1, 2, 3};
Output: Index of local minima is 0

Input: arr[] = {3, 2, 1};
Output: Index of local minima is 2

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

هناك طريقتان لحلّ هذه المسألة:

1. الطريقة الأولى هي الطريقة البسيطة وتتضمّن استخدام عملية بحث خطّي في المصفوفة وعند العثور على صغرى محلية تعيد الخوارزمية النتيجة. يبلغ التعقيد الزمني للحالة السوأى في هذه الطريقة المقدار O(n).
2. تعتمد الطريقة الثانية على خوارزمية البحث الثنائي. إذ تقارن العنصر الوسطي مع العنصرين المجاورين له، فإن لم يكن العنصر الوسطي أكبر من مجاوريه تعيد الخوارزمية العنصر الوسطي. أما إن كان العنصر الوسطي أكبر من جاره الأيسر فهذا يعني لزوم وجود صغرى محلية في النصف الأيسر من المصفوفة، وإن كان العنصر الوسطي أكبر من جاره الأيمن فهذا يعني لزوم وجود صغرى محلية في النصف الأيمن من المصفوفة.

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

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

• C++‎:

#include <stdio.h> 

// تستخدم الدالة خوارزمية البحث الثنائي
// لتعيد قيمة الصغرى المحلية
int localMinUtil(int arr[], int low, int high, int n) 
{ 
	// إيجاد موقع العنصر الوسطي
	// Find index of middle element 
	int mid = low + (high - low)/2; /* (low + high)/2 يمكن كذلك استخدام الصيغة */

	// مقارنة العنصر الوسطي مع جاريه
	// (إن كان هناك جاران)
	if ((mid == 0 || arr[mid-1] > arr[mid]) && 
			(mid == n-1 || arr[mid+1] > arr[mid])) 
		return mid; 

	// إن لم يكن العنصر الوسطي صغرى محلية وكان جاره الأيسر أصغر منه
	// فإنّ الصغرى المحلية ستكون حتمًا في النصف الأيسر من المصفوفة
	
	else if (mid > 0 && arr[mid-1] < arr[mid]) 
		return localMinUtil(arr, low, (mid -1), n); 

	// إن لم يكن العنصر الوسطي صغرى محلية وكان جاره الأيمن أصغر منه
	// فإنّ الصغرى المحلية ستكون حتمًا في النصف الأيمن من المصفوفة

	return localMinUtil(arr, (mid + 1), high, n); 
} 

// استدعاء الدالة السابقة
int localMin(int arr[], int n) 
{ 
	return localMinUtil(arr, 0, n-1, n); 
} 

/* اختبار الدالتين السابقتين */
int main() 
{ 
	int arr[] = {4, 3, 1, 14, 16, 40}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	printf("Index of a local minima is %d", 
						localMin(arr, n)); 
	return 0; 
}

• بايثون:

# تستخدم الدالة خوارزمية البحث الثنائي 
# لتعيد قيمة الصغرى المحلية
def localMinUtil(arr, low, high, n): 
		
	# إيجاد موقع العنصر الوسطي 
	mid = low + (high - low) / 2
		
	#  مقارنة العنصر الوسطي مع جاريه
	# (إن كان هناك جاران)
	if(mid == 0 or arr[mid - 1] > arr[mid] and
	mid == n - 1 or arr[mid] < arr[mid + 1]): 
		return mid 
		
	# إن لم يكن العنصر الوسطي صغرى محلية وكان جاره الأيسر أصغر منه
	# فإنّ الصغرى المحلية ستكون حتمًا في النصف الأيسر من المصفوفة
	elif(mid > 0 and arr[mid - 1] < arr[mid]): 
		return localMinUtil(arr, low, mid - 1, n) 
		
	# إن لم يكن العنصر الوسطي صغرى محلية وكان جاره الأيمن أصغر منه
	# فإنّ الصغرى المحلية ستكون حتمًا في النصف الأيمن من المصفوفة
	return localMinUtil(arr, mid + 1, high, n) 
	
# استدعاء الدالة السابقة 
def localMin(arr, n): 
	
	return localMinUtil(arr, 0, n - 1, n) 
	
# اختبار الدالتين السابقتين
arr = [4, 3, 1, 14, 16, 40] 
n = len(arr) 
print("Index of a local minima is " , 
					localMin(arr, n))

• جافا:

import java.io.*; 

class GFG 
{ 
	
	// يستخدم التابع خوارزمية البحث الثنائي
    // ليعيد قيمة الصغرى المحلية. 
	public static int localMinUtil(int[] arr, int low, 
								int high, int n) 
	{ 
		
		// إيجاد موقع العنصر الوسطي 
		int mid = low + (high - low) / 2; 
		
		// مقارنة العنصر الوسطي مع جاريه 
		// (إن كان هناك جاران) 
		if(mid == 0 || arr[mid - 1] > arr[mid] && mid == n - 1 || 
		arr[mid] < arr[mid + 1]) 
				return mid; 
		
		// إن لم يكن العنصر الوسطي صغرى محلية وكان جاره الأيسر أصغر منه
		// فإنّ الصغرى المحلية ستكون حتمًا في النصف الأيسر من المصفوفة
		else if(mid > 0 && arr[mid - 1] < arr[mid]) 
				return localMinUtil(arr, low, mid - 1, n); 
		
		// إن لم يكن العنصر الوسطي صغرى محلية وكان جاره الأيمن أصغر منه
		// فإنّ الصغرى المحلية ستكون حتمًا في النصف الأيمن من المصفوفة
		return localMinUtil(arr, mid + 1, high, n); 
	} 
	
	// استدعاء التابع السابق
	public static int localMin(int[] arr, int n) 
	{ 
		return localMinUtil(arr, 0, n - 1, n); 
	} 
	
	// اختبار التابعين السابقين
	public static void main (String[] args) 
	{ 
		
		int arr[] = {4, 3, 1, 14, 16, 40}; 
		int n = arr.length; 
		System.out.println("Index of a local minima is " + localMin(arr, n)); 
	
	} 
}

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

Index of a local minima is 2

التعقيد الزمني

يبلغ التعقيد الزمني لهذه الخوارزمية المقدار O(Log n)‎.

مصادر

• صفحة Find a local minima in an array في توثيق الخوارزميات في موقع GeeksforGeeks.