الفرق بين المراجعتين ل"Algorithms/floor sorted array"
اذهب إلى التنقل
اذهب إلى البحث
(أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE:إيجاد أكبر عنصر في مصفوفة مرتبة يكون أصغر من العنصر المعطى}}</noinclude> المطلوب في ه...') |
|||
| سطر 2: | سطر 2: | ||
المطلوب في هذه المسألة هو إيجاد أكبر عنصر في مصفوفة مرتبة يكون أصغر من العنصر المعطى (ليكن <code>x</code>)، يسمّى هذا العنصر بأرضية العنصر <code>x</code>. | المطلوب في هذه المسألة هو إيجاد أكبر عنصر في مصفوفة مرتبة يكون أصغر من العنصر المعطى (ليكن <code>x</code>)، يسمّى هذا العنصر بأرضية العنصر <code>x</code>. | ||
| − | '''مثال:''' | + | '''مثال:'''<syntaxhighlight lang="text"> |
| − | + | Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 5 | |
| − | < | ||
Output : 2 | Output : 2 | ||
العدد 2 هو أكبر عنصر في المصفوفة يكون أصغر من 5 | العدد 2 هو أكبر عنصر في المصفوفة يكون أصغر من 5 | ||
| سطر 14: | سطر 13: | ||
Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 0 | Input : arr[] = {1, 2, 8, 10, 10, 12, 19}, x = 0 | ||
Output : -1 | Output : -1 | ||
| − | لا يوجد أرضية للعدد المعطى لذا تكون المخرجات -1</ | + | لا يوجد أرضية للعدد المعطى لذا تكون المخرجات -1 |
| + | </syntaxhighlight> | ||
| + | |||
== الطريقة البسيطة == | == الطريقة البسيطة == | ||
| سطر 108: | سطر 109: | ||
== استخدام البحث الثنائي == | == استخدام البحث الثنائي == | ||
| − | يمكن استخدام خوارزمية البحث الثنائي لإيجاد العنصر المطلوب. | + | يمكن استخدام خوارزمية [[Algorithms/binary search|البحث الثنائي]] لإيجاد العنصر المطلوب. |
=== تنفيذ الخوارزمية === | === تنفيذ الخوارزمية === | ||
المراجعة الحالية بتاريخ 18:31، 24 ديسمبر 2019
المطلوب في هذه المسألة هو إيجاد أكبر عنصر في مصفوفة مرتبة يكون أصغر من العنصر المعطى (ليكن 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.