عرض مصدر Algorithms/floor sorted array

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

'''مثال:'''<syntaxhighlight lang="text">
Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 5
Output : 2
العدد 2 هو أكبر عنصر في المصفوفة يكون أصغر من 5

Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 20
Output : 19
العدد 19 هو أكبر عنصر في المصفوفة يكون أصغر من 20

Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 0
Output : -1
لا يوجد أرضية للعدد المعطى لذا تكون المخرجات -1
</syntaxhighlight>

== الطريقة البسيطة ==

يمكن حلّ هذه المسألة بطريقة بسيطة وذلك بالتنقل عبر عناصر المصفوفة المرتبة والبحث عن أوّل عنصر يكون أكبر من العنصر المعطى <code>x</code>. وتكون أرضية العنصر <code>x</code> هي العنصر الذي يسبق العنصر الذي عثرت عليه الخوارزمية.

* C++‎:

<source lang="c++">#include<stdio.h> 

int floorSearch(int arr[], int n, int x) 
{ 
	// إن كان العنصر الأخير أصغر من العنصر المعطى
	if (x >= arr[n-1]) 
		return n-1; 

	// إن كان العنصر الأول أكبر من العنصر المعطى
	if (x < arr[0]) 
		return -1; 

	// إجراء عملية بحث خطي عن أول عنصر يكون أكبر من العنصر المعطى
	for (int i=1; i<n; i++) 
	if (arr[i] > x) 
		return (i-1); 

	return -1; 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	int arr[] = {1, 2, 4, 6, 10, 12, 14}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	int x = 7; 
	int index = floorSearch(arr, n-1, x); 
	if (index == -1) 
		printf("Floor of %d doesn't exist in array ", x); 
	else
		printf("Floor of %d is %d", x, arr[index]); 
	return 0; 
} 
</source>
* بايثون:

<source lang="python">
</source>
* جافا:

<source lang="java">import java.io.*; 
import java.util.*; 
import java.lang.*; 

class GFG 
{ 

static int floorSearch(int arr[], int n, int x) 
{ 
	// إن كان العنصر الأخير أصغر من العنصر المعطى
	if (x >= arr[n-1]) 
		return n-1; 

	// إن كان العنصر الأول أكبر من العنصر المعطى 
	if (x < arr[0]) 
		return -1; 

	// إجراء عملية بحث خطي عن أول عنصر يكون أكبر من العنصر المعطى 
	for (int i=1; i<n; i++) 
	if (arr[i] > x) 
		return (i-1); 

	return -1; 
} 

// اختبار الدالة السابقة 
public static void main(String[] args) 
{ 
	int arr[] = {1, 2, 4, 6, 10, 12, 14}; 
	int n = arr.length; 
	int x = 7; 
	int index = floorSearch(arr, n-1, x); 
	if (index == -1) 
		System.out.print("Floor of " + x + " doesn't exist in array "); 
	else
		System.out.print("Floor of " + x + " is "+ arr[index]); 
} 
} </source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">Floor of 7 is 6.</source>
=== التعقيد الزمني ===

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

== استخدام البحث الثنائي ==

يمكن استخدام خوارزمية [[Algorithms/binary search|البحث الثنائي]] لإيجاد العنصر المطلوب.

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

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

* C++‎:

<source lang="c++">#include<stdio.h> 

int floorSearch(int arr[], int low, int high, int x) 
{ 
	// إن تقاطع الحدان الأعلى والأدنى مع بعضهما البعض
	if (low > high) 
		return -1; 

	// إن كان العنصر الأخير أصغر من العنصر المعطى
	if (x >= arr[high]) 
		return high; 

	// إيجاد نقطة الوسط
	int mid = (low+high)/2; 

	// إن كانت نقطة الوسط هي أرضية العنصر المعطى
	if (arr[mid] == x) 
		return mid; 

	// إن كان العنصر المعطى يقع بين
	//mid و mid-1
	if (mid > 0 && arr[mid-1] <= x && x < arr[mid]) 
		return mid-1; 

	// إن كان العنصر المعطى أصغر من نقطة الوسط
	// فيلزم حينئذٍ أن تكون أرضية العنصر المعطى في النصف الأيسر
	if (x < arr[mid]) 
		return floorSearch(arr, low, mid-1, x); 
    
    // إن لم يكن العنصر الذي يسبق نقطة الوسط هو أرضية العنصر المعطى
    // arr[mid] وكان العنصر المعطى أكبر من
	return floorSearch(arr, mid+1, high, x); 
} 

/* اختبار الدالة السابقة */
int main() 
{ 
	int arr[] = {1, 2, 4, 6, 10, 12, 14}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	int x = 7; 
	int index = floorSearch(arr, 0, n-1, x); 
	if (index == -1) 
		printf("Floor of %d doesn't exist in array ", x); 
	else
		printf("Floor of %d is %d", x, arr[index]); 
	return 0; 
} 
</source>
* بايثون:

<source lang="python">def floorSearch(arr, low, high, x): 

	# إن تقاطع الحدان الأعلى والأدنى مع بعضهما البعض
	if (low > high): 
		return -1

	# إن كان العنصر الأخير أصغر من العنصر المعطى
	if (x >= arr[high]): 
		return high 

	# إيجاد نقطة الوسط
	mid = int((low + high) / 2) 

	# إن كانت نقطة الوسط هي أرضية العنصر المعطى 
	if (arr[mid] == x): 
		return mid 

	#  إن كان العنصر المعطى يقع بين
	# mid-1 و mid 
	if (mid > 0 and arr[mid-1] <= x 
				and x < arr[mid]): 
		return mid - 1

	# إن كان العنصر المعطى أصغر من نقطة الوسط 
	# فيلزم حينئذٍ أن تكون أرضية العنصر المعطى في النصف الأيسر 
	if (x < arr[mid]): 
		return floorSearch(arr, low, mid-1, x) 

	# إن لم يكن العنصر الذي يسبق نقطة الوسط هو أرضية العنصر المعطى
	# arr[mid] وكان العنصر المعطى أكبر من
	return floorSearch(arr, mid+1, high, x) 


# اختبار الدالة السابقة
arr = [1, 2, 4, 6, 10, 12, 14] 
n = len(arr) 
x = 7
index = floorSearch(arr, 0, n-1, x) 

if (index == -1): 
	print("Floor of", x, "doesn't exist\ 
					in array ", end = "") 
else: 
	print("Floor of", x, "is", arr[index]) 

# This code is contributed by Smitha Dinesh Semwal. 
</source>
* جافا:

<source lang="java">import java.io.*; 

class GFG { 
	
	static int floorSearch(int arr[], int low, 
							int high, int x) 
	{ 
		// إن تقاطع الحدان الأعلى والأدنى مع بعضهما البعض 
		if (low > high) 
			return -1; 

		// إن كان العنصر الأخير أصغر من العنصر المعطى 
		if (x >= arr[high]) 
			return high; 

		// إيجاد نقطة الوسط
		int mid = (low+high)/2; 

		// إن كانت نقطة الوسط هي أرضية العنصر المعطى 
		if (arr[mid] == x) 
			return mid; 

		// إن كان العنصر المعطى يقع بين
		// mid-1 و mid 
		if (mid > 0 && arr[mid-1] <= x && x < 
									arr[mid]) 
			return mid-1; 

		// إن كان العنصر المعطى أصغر من نقطة الوسط 
		// فيلزم حينئذٍ أن تكون أرضية العنصر المعطى في النصف الأيسر
		if (x < arr[mid]) 
			return floorSearch(arr, low, 
							mid - 1, x); 

		// إن لم يكن العنصر الذي يسبق نقطة الوسط هو أرضية العنصر المعطى
		// arr[mid] وكان العنصر المعطى أكبر من 
		return floorSearch(arr, mid + 1, high, 
										x); 
	} 

	/* اختبار الدالة السابقة */
	public static void main(String[] args) 
	{ 
		int arr[] = {1, 2, 4, 6, 10, 12, 14}; 
		int n = arr.length; 
		int x = 7; 
		int index = floorSearch(arr, 0, n - 1, 
										x); 
		if (index == -1) 
			System.out.println("Floor of " + x + 
					" dosen't exist in array "); 
		else
			System.out.println("Floor of " + x + 
							" is " + arr[index]); 
	} 
} </source>
تعطي الشيفرات السابقة المخرجات التالية:

<source lang="text">Floor of 7 is 6.</source>
=== التعقيد الزمني ===

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

== مصادر ==

* صفحة [https://www.geeksforgeeks.org/floor-in-a-sorted-array/ Floor in a Sorted Array] في توثيق الخوارزميات في موقع GeeksforGeeks.

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