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

المطلوب في هذه المسألة هو إيجاد أكبر عنصر في مصفوفة مرتبة يكون أصغر من العنصر المعطى (ليكن 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)‎.

مصادر

• صفحة Floor in a Sorted Array في توثيق الخوارزميات في موقع GeeksforGeeks.