الفرق بين المراجعتين لصفحة: «Ruby/Range/bsearch»
أنشأ الصفحة ب'<noinclude>{{DISPLAYTITLE: التابع <code>bsearch</code> الخاص بالصنف <code>Range</code> في روبي}}</noinclude> تصنيف: Ruby تصني...' |
لا ملخص تعديل |
||
| سطر 3: | سطر 3: | ||
[[تصنيف: Ruby Method]] | [[تصنيف: Ruby Method]] | ||
[[تصنيف: Ruby Range]] | [[تصنيف: Ruby Range]] | ||
باستخدام البحث الثنائي (binary search)، يبحث التابع <code>bsearch</code> عن قيمة من المجال تفي بالشرط المعطى في مدة O (log n) حيث n | باستخدام خوارزمية البحث الثنائي (binary search)، يبحث التابع <code>bsearch</code> عن قيمة من المجال تفي بالشرط المعطى في مدة O (log n) ، حيث n يمثل حجم المجال. | ||
يمكنك استخدام هذا التابع بطريقتين: وضع البحث الأدنى (find-minimum mode)، أو وضع البحث العادي (find-any mode). وفي كلتا الحالتين، يجب أن تكون عناصر المجال مُرتبة (sorted) لأجل الكتلة. | |||
يجب عدم خلط الوضعين في وقت واحد؛ يجب أن | في وضع البحث الأدنى (يعد هذا خيارًا جيدًا في الحالات العادية)، يجب أن تُعيد الكتلة إما <code>true</code> أو <code>false</code>، ويجب أن تكون هناك قيمة <code>x</code> بحيث: | ||
* تعيد الكتلة القيمة <code>false</code> لكل القيم الأصغر من <code>x</code>، | |||
* تعيد <code>true</code> لأي قيمة أكبر من أو تساوي <code>x</code>. | |||
إن كان <code>x</code> مُتضمنًا في المجال، فسيعيد التابع القيمة <code>x</code>. خلا ذلك، فسيعيد الصفر.<syntaxhighlight lang="ruby">ary = [0, 4, 7, 10, 12] | |||
(0...ary.size).bsearch {|i| ary[i] >= 4 } #=> 1 | |||
(0...ary.size).bsearch {|i| ary[i] >= 6 } #=> 2 | |||
(0...ary.size).bsearch {|i| ary[i] >= 8 } #=> 3 | |||
(0...ary.size).bsearch {|i| ary[i] >= 100 } #=> nil | |||
(0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0</syntaxhighlight>في وضع البحث العادي (سلوكه يشبه سلوك <code>bsearch(3)</code>)، يجب أن تعيد الكتلة عددًا، ويجب أن تكون هناك قيمتان <code>x</code> و <code>y</code> (تحققان x <= y) بحيث: | |||
* تعيد الكتلة عددًا موجبًا لكل v بحيث v <x، | |||
* تعيد الكتلة الصفر لـكل v يحقق x <= v <y، | |||
* تعيد الكتلة عددًا سالبًا لكل v يحقق y <= v. | |||
يعيد هذا التابع أي قيمة ضمن تقاطع المجال المحدد و <code>x… y</code> (إن وجدت). إن لم تكن هناك أي قيمة تحقق هذا الشرط، فستُعاد <code>nil</code>. | |||
يجب عدم خلط الوضعين في وقت واحد؛ يجب أن تعيد الكتلة دائمًا إما <code>true</code> أو <code>false</code>، أو تعيد دائمًا عددًا. | |||
لا يمكن معرفة القيمة المُلتقطة في كل عملية تكرار (iteration). | |||
==البنية العامة== | ==البنية العامة== | ||
<syntaxhighlight lang="ruby">bsearch {|obj| block } → value</syntaxhighlight> | <syntaxhighlight lang="ruby">bsearch {|obj| block } → value</syntaxhighlight> | ||
| سطر 19: | سطر 30: | ||
==أمثلة== | ==أمثلة== | ||
مثال على استخدام التابع <code>bsearch</code> | |||
=== مثال على استخدام التابع <code>bsearch</code> وفق وضع البحث الأدنى === | |||
<syntaxhighlight lang="ruby">ary = [0, 4, 7, 10, 12] | <syntaxhighlight lang="ruby">ary = [0, 4, 7, 10, 12] | ||
(0...ary.size).bsearch {|i| ary[i] >= 4 } #=> 1 | (0...ary.size).bsearch {|i| ary[i] >= 4 } #=> 1 | ||
| سطر 26: | سطر 38: | ||
(0...ary.size).bsearch {|i| ary[i] >= 100 } #=> nil | (0...ary.size).bsearch {|i| ary[i] >= 100 } #=> nil | ||
(0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0</syntaxhighlight> | (0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0</syntaxhighlight> | ||
=== مثال على استخدام التابع <code>bsearch</code> وفق وضع البحث العادي === | |||
<syntaxhighlight lang="ruby">ary = [0, 100, 100, 100, 200] | |||
(0..4).bsearch {|i| 100 - ary[i] } #=> 1, 2 or 3 | |||
(0..4).bsearch {|i| 300 - ary[i] } #=> nil | |||
(0..4).bsearch {|i| 50 - ary[i] } #=> nil</syntaxhighlight> | |||
==انظر أيضا== | ==انظر أيضا== | ||
* التابع <code>[[Ruby/Range/begin|begin]]</code>: يعيد الكائن الذي يحدد بداية المجال. | * التابع <code>[[Ruby/Range/begin|begin]]</code>: يعيد الكائن الذي يحدد بداية المجال. | ||
مراجعة 17:16، 30 أكتوبر 2018
باستخدام خوارزمية البحث الثنائي (binary search)، يبحث التابع bsearch عن قيمة من المجال تفي بالشرط المعطى في مدة O (log n) ، حيث n يمثل حجم المجال.
يمكنك استخدام هذا التابع بطريقتين: وضع البحث الأدنى (find-minimum mode)، أو وضع البحث العادي (find-any mode). وفي كلتا الحالتين، يجب أن تكون عناصر المجال مُرتبة (sorted) لأجل الكتلة.
في وضع البحث الأدنى (يعد هذا خيارًا جيدًا في الحالات العادية)، يجب أن تُعيد الكتلة إما true أو false، ويجب أن تكون هناك قيمة x بحيث:
- تعيد الكتلة القيمة
falseلكل القيم الأصغر منx، - تعيد
trueلأي قيمة أكبر من أو تساويx.
إن كان x مُتضمنًا في المجال، فسيعيد التابع القيمة x. خلا ذلك، فسيعيد الصفر.
ary = [0, 4, 7, 10, 12]
(0...ary.size).bsearch {|i| ary[i] >= 4 } #=> 1
(0...ary.size).bsearch {|i| ary[i] >= 6 } #=> 2
(0...ary.size).bsearch {|i| ary[i] >= 8 } #=> 3
(0...ary.size).bsearch {|i| ary[i] >= 100 } #=> nil
(0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0
في وضع البحث العادي (سلوكه يشبه سلوك bsearch(3))، يجب أن تعيد الكتلة عددًا، ويجب أن تكون هناك قيمتان x و y (تحققان x <= y) بحيث:
- تعيد الكتلة عددًا موجبًا لكل v بحيث v <x،
- تعيد الكتلة الصفر لـكل v يحقق x <= v <y،
- تعيد الكتلة عددًا سالبًا لكل v يحقق y <= v.
يعيد هذا التابع أي قيمة ضمن تقاطع المجال المحدد و x… y (إن وجدت). إن لم تكن هناك أي قيمة تحقق هذا الشرط، فستُعاد nil.
يجب عدم خلط الوضعين في وقت واحد؛ يجب أن تعيد الكتلة دائمًا إما true أو false، أو تعيد دائمًا عددًا.
لا يمكن معرفة القيمة المُلتقطة في كل عملية تكرار (iteration).
البنية العامة
bsearch {|obj| block } → value
القيمة المُعادة
أمثلة
مثال على استخدام التابع bsearch وفق وضع البحث الأدنى
ary = [0, 4, 7, 10, 12]
(0...ary.size).bsearch {|i| ary[i] >= 4 } #=> 1
(0...ary.size).bsearch {|i| ary[i] >= 6 } #=> 2
(0...ary.size).bsearch {|i| ary[i] >= 8 } #=> 3
(0...ary.size).bsearch {|i| ary[i] >= 100 } #=> nil
(0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0
مثال على استخدام التابع bsearch وفق وضع البحث العادي
ary = [0, 100, 100, 100, 200]
(0..4).bsearch {|i| 100 - ary[i] } #=> 1, 2 or 3
(0..4).bsearch {|i| 300 - ary[i] } #=> nil
(0..4).bsearch {|i| 50 - ary[i] } #=> nil
انظر أيضا
- التابع
begin: يعيد الكائن الذي يحدد بداية المجال. - التابع
cover?: يعيد القيمةtrueإن كانobjمحصورًا بين بداية ونهاية المجال.