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

من موسوعة حسوب
اذهب إلى: تصفح، ابحث

المطلوب في هذه المسألة هو إيجاد أكبر عنصر في مصفوفة مرتبة يكون أصغر من العنصر المعطى (ليكن x)، يسمّى هذا العنصر بأرضية العنصر x.

مثال:
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

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

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

  • 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; 
}
  • بايثون:

  • جافا:
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]); 
} 
}

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

Floor of 7 is 6.

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

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

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

يمكن استخدام خوارزمية البحث الثنائي لإيجاد العنصر المطلوب.

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

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

  • 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; 
}
  • بايثون:
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.
  • جافا:
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]); 
	} 
}

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

Floor of 7 is 6.

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

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

مصادر