إيجاد ذروة المصفوفة

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

فعلى سبيل المثال يمثّل العنصر 20 ذروة المصفوفة ‎{5, 10, 20, 15}، أما المصفوفة ‎{10, 20, 15, 2, 23, 90, 67}‎ فتحتوي على ذروتين هما 20 و 90، ويمكن إعادة إحدى الذروتين.

وهناك بعض الحالات الخاصة في هذه المسألة:

1. إن كانت المصفوفة المدخلة مرتّبة تصاعديًا، فإنّ العنصر الأخير يكون ذروة المصفوفة. يمثّل العنصر 50 ذروة المصفوفة ‎{10, 20, 30, 40, 50‎}‎.
2. إن كانت المصفوفة المدخلة مرتّبة تنازليًا، فإنّ العنصر الأول يكون ذورة المصفوفة. يمثّل العنصر 100 ذروة المصفوفة ‎{100, 80, 60, 50, 20}‎.
3. إن كانت جميع العناصر في المصفوفة متساوية، فإنّ كل عنصر من هذه العناصر يمثّل ذروة المصفوفة.

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

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

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

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

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

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

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// تستخدم هذه الدالة خوارزمية البحث الثنائي
// لتعيد موقع ذروة المصفوفة المعطاة
int findPeakUtil(int arr[], int low, 
				int high, int n) 
{ 
	// إيجاد موقع العنصر الوسطي
	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 findPeakUtil(arr, low, (mid - 1), n); 

	// إن لم يكن العنصر الوسطي هو ذروة المصفوفة
	// وكان جاره الأيمن أكبر منه، فهذا يعني
	// أن النصف الأيمن من المصفوفة يحتوي على ذروتها حتمًا
		else return findPeakUtil(arr, (mid + 1), high, n); 
} 

// تستدعي هذه الدالة الدالة السابقة
int findPeak(int arr[], int n) 
{ 
	return findPeakUtil(arr, 0, n - 1, n); 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int arr[] = {1, 3, 20, 4, 1, 0}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	cout << "Index of a peak point is "
		<< findPeak(arr, n); 
	return 0; 
}

• بايثون:

# تستخدم هذه الدالة خوارزمية البحث الثنائي 
# لتعيد موقع ذروة المصفوفة المعطاة 
def findPeakUtil(arr, low, high, n): 
	
	# إيجاد موقع العنصر الوسطي
	# (low + high)/2 
	mid = low + (high - low)/2
	mid = int(mid) 
	
	# مقارنة العنصر الوسطي بالعنصرين المجاورين له (إن وجدا) 
	if ((mid == 0 or arr[mid - 1] <= arr[mid]) and
	(mid == n - 1 or arr[mid + 1] <= arr[mid])): 
		return mid 


	# إن لم يكن العنصر الوسطي هو ذروة المصفوفة
	# its left neighbour is greater 
	# وكان جاره الأيسر أكبر منه، فهذا يعني
	# أن النصف الأيسر من المصفوفة يحتوي على ذروتها حتمًا
	elif (mid > 0 and arr[mid - 1] > arr[mid]): 
		return findPeakUtil(arr, low, (mid - 1), n) 

	# إن لم يكن العنصر الوسطي هو ذروة المصفوفة
	# وكان جاره الأيمن أكبر منه، فهذا يعني
	# أن النصف الأيمن من المصفوفة يحتوي على ذروتها حتمًا 
	else: 
		return findPeakUtil(arr, (mid + 1), high, n) 


# تستدعي هذه الدالة الدالة السابقة 
def findPeak(arr, n): 

	return findPeakUtil(arr, 0, n - 1, n) 


# اختبار الدالة السابقة
arr = [1, 3, 20, 4, 1, 0] 
n = len(arr) 
print("Index of a peak point is", findPeak(arr, n))

• جافا:

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

class PeakElement 
{ 
	// يستخدم هذا التابع خوارزمية البحث الثنائي 
	// ليعيد موقع ذروة المصفوفة المعطاة
	static int findPeakUtil(int arr[], int low, int high, int n) 
	{ 
		// إيجاد موقع العنصر الوسطي 
		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 findPeakUtil(arr, low, (mid -1), n); 

		// إن لم يكن العنصر الوسطي هو ذروة المصفوفة 
		// وكان جاره الأيمن أكبر منه، فهذا يعني 
		// أن النصف الأيمن من المصفوفة يحتوي على ذروتها حتمًا
		else return findPeakUtil(arr, (mid + 1), high, n); 
	} 

	// يستدعي هذا التابع التابع السابق 
	static int findPeak(int arr[], int n) 
	{ 
		return findPeakUtil(arr, 0, n-1, n); 
	} 

	// اختبار التابع السابق 
	public static void main (String[] args) 
	{ 
		int arr[] = {1, 3, 20, 4, 1, 0}; 
		int n = arr.length; 
		System.out.println("Index of a peak point is " + 
							findPeak(arr, n)); 
	} 
}

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

Index of a peak point is 2

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

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

مصادر

• صفحة Find a peak element في توثيق الخوارزميات في موقع GeeksforGeeks.