عرض مصدر Algorithms/repeating element

<noinclude>{{DISPLAYTITLE:إيجاد العنصر المكرّر في المصفوفة}}</noinclude>
المطلوب في هذه المسألة هو إيجاد العنصر المكرّر في مصفوفة تحتوي على مجموعة من العناصر المرتّبة، ويتكرّر فيها عنصر واحد فقط.

'''مثال:'''

<source lang="text">Input :  arr[] = { 1, 2 , 3 , 4 , 4}
Output :  4

Input :  arr[] = { 1 , 1 , 2 , 3 , 4}
Output :  1</source>
== خطوات الخوارزمية ==

الحل البسيط هو المرور على المصفوفة بأكملها والتحقق من أن العنصر الحالي مكرّر، ثم يُعاد العنصر المكرر إن وجد. يبلغ التعقيد الزمني لهذه الطريقة المقدار <code>O(n)‎</code>.

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

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

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

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

* C++‎:

<source lang="c++">#include <bits/stdc++.h> 
using namespace std; 

// تعيد الدالة موقع الظهور الثاني للعنصر المكرر
// n-1 تفترض الدالة أنّ عناصر المصفوفة تتدرج ضمن النطاق 1 إلى 
int findRepeatingElement(int arr[], int low, int high) 
{ 
	// low = 0 , high = n-1; 
	if (low > high) 
		return -1; 

	int mid = (low + high) / 2; 

	// التحقق من كون العنصر الوسطي هو العنصر المكرر
	if (arr[mid] != mid + 1) 
	{ 
		if (mid > 0 && arr[mid]==arr[mid-1]) 
			return mid; 

		// إن لم يكن العنصر الوسطي في موقعه الصحيح
		// فهذا يعني أنّ العنصر المكرر سيكون إلى يساره
		return findRepeatingElement(arr, low, mid-1); 
	} 

	// إن كان العنصر الوسطي في موقعه الصحيح
	// فإنّ العنصر المكرّر سيكون إلى يمينه
	return findRepeatingElement(arr, mid+1, high); 
} 

// اختبار الدالة السابقة 
int main() 
{ 
	int arr[] = {1, 2, 3, 3, 4, 5}; 
	int n = sizeof(arr) / sizeof(arr[0]); 
	int index = findRepeatingElement(arr, 0, n-1); 
	if (index != -1) 
		cout << arr[index]; 
	return 0; 
} 
</source>
* بايثون:

<source lang="python"># تعيد الدالة موقع الظهور الثاني للعنصر المكرر
# n-1 تفترض الدالة أنّ عناصر المصفوفة تتدرج ضمن النطاق 1 إلى 
def findRepeatingElement(arr, low, high): 

	# low = 0 , high = n-1 
	if low > high: 
		return -1

	mid = (low + high) / 2

	# التحقق من كون العنصر الوسطي هو العنصر المكرر
	if (arr[mid] != mid + 1): 
	
		if (mid > 0 and arr[mid]==arr[mid-1]): 
			return mid 

		# إن لم يكن العنصر الوسطي في موقعه الصحيح 
		# فهذا يعني أنّ العنصر المكرر سيكون إلى يساره
		return findRepeatingElement(arr, low, mid-1) 

	# إن كان العنصر الوسطي في موقعه الصحيح 
	# فإنّ العنصر المكرّر سيكون إلى يمينه
	return findRepeatingElement(arr, mid+1, high) 

# اختبار الدالة السابقة 
arr = [1, 2, 3, 3, 4, 5] 
n = len(arr) 
index = findRepeatingElement(arr, 0, n-1) 
if (index is not -1): 
	print arr[index] 

#اختبار الدالة السابقة 
</source>
* جافا:

<source lang="java">class Test 
{ 
	// يعيد التابع موقع الظهور الثاني للعنصر المكرر
	//  n-1 تفترض الدالة أنّ عناصر المصفوفة تتدرج ضمن النطاق 1 إلى  
	static int findRepeatingElement(int arr[], int low, int high) 
	{ 
		// low = 0 , high = n-1; 
		if (low > high) 
			return -1; 
	
		int mid = (low + high) / 2; 
	
		// التحقق من كون العنصر الوسطي هو العنصر المكرر 
		if (arr[mid] != mid + 1) 
		{ 
			if (mid > 0 && arr[mid]==arr[mid-1]) 
				return mid; 
	
			// إن لم يكن العنصر الوسطي في موقعه الصحيح 
			// فهذا يعني أنّ العنصر المكرر سيكون إلى يساره 
			return findRepeatingElement(arr, low, mid-1); 
		} 
	
		// إن كان العنصر الوسطي في موقعه الصحيح 
		// فإنّ العنصر المكرّر سيكون إلى يمينه
		return findRepeatingElement(arr, mid+1, high); 
	} 
	
	// اختبار التابع السابق
	public static void main(String[] args) 
	{ 
		int arr[] = {1, 2, 3, 3, 4, 5}; 
		int index = findRepeatingElement(arr, 0, arr.length-1); 
		if (index != -1) 
			System.out.println(arr[index]); 
	} 
} 
</source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">3</source>
== التعقيد الزمني ==

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

== مصادر ==

* صفحة [https://www.geeksforgeeks.org/find-repeating-element-sorted-array-size-n/ Find the only repeating element in a sorted array of size n] في توثيق الخوارزميات في موقع GeeksforGeeks.

[[تصنيف: الخوارزميات]]
[[تصنيف: فرق تسد]]