الفرق بين المراجعتين لصفحة: «Ruby/Range/bsearch»

المراجعة الحالية بتاريخ 06:13، 3 ديسمبر 2018

يبحث التابع bsearch باستخدام خوارزمية البحث الثنائي (binary search) عن قيمة من المجال تحقق الشرط المعطى في مدةO (log n) ‎، إذ n يمثل حجم المجال.

البنية العامة

bsearch {|obj| block }  → value‎

يمكنك استخدام هذا التابع بطريقتين: وضع البحث الأدنى (find-minimum mode)، أو وضع البحث العادي (find-any mode). وفي كلتا الحالتين، يجب أن تكون عناصر المجال مُرتبة (sorted) لأجل الكتلة.

في وضع البحث الأدنى (يعد هذا خيارًا جيدًا في الحالات العادية)، يجب أن تُعيد الكتلة إما true أو false، ويجب أن تكون هناك قيمة x بحيث:

تعيد الكتلة القيمة false لكل القيم الأصغر من x، و
تعيد القيمة true لأي قيمة أكبر من أو تساوي x.

إن كان x مُتضمنًا في المجال، فسيعيد التابع القيمة x. خلا ذلك، فسيعيد صفرًا.

في وضع البحث العادي (سلوكه يشبه سلوك bsearch(3)‎)، يجب أن تعيد الكتلة عددًا، ويجب أن تكون هناك قيمتان x و y (تحققان x <= y) بحيث:

تعيد الكتلة عددًا موجبًا لكل v بحيث v < x، و
تعيد الكتلة الصفر لكل v يحقق x <= v < y، و
تعيد الكتلة عددًا سالبًا لكل v يحقق y <= v.

يعيد هذا التابع أي قيمة ضمن تقاطع المجال المحدد و x…y (إن وجدت). إن لم تكن هناك أية قيمة تحقق هذا الشرط، فستُعاد القيمة nil.

يجب عدم خلط الوضعين في وقت واحد؛ يجب أن تعيد الكتلة دائمًا إما true أو false، أو تعيد دائمًا عددًا.

لا يمكن معرفة القيمة المُلتقطة في كل عملية تكرار (iteration).

‎القيمة المعادة

تعاد إمَّا القيمة true أو القيمة false إن استُعمل وضع البحث الأدنى، أو تعاد قيمة عددية أو القيمة nil إن استعمل وضع البحث العادي (اطلع على قسم البينة العامة لمزيد من التفاصيل).

أمثلة

مثال على استخدام التابع 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?‎: يتحقق إن كان الكائن المُمرَّر إليه محصورًا بين بداية ونهاية المجال.

مصادر

قسم التابع bsearch‎ في الصنف Range‎ في توثيق روبي الرسمي.

@@ سطر 1: / سطر 1: @@
-<noinclude>{{DISPLAYTITLE: التابع <code>bsearch‎</code> الخاص بالصنف <code>Range</code> في روبي}}</noinclude>
+<noinclude>{{DISPLAYTITLE: التابع <code>Range.bsearch‎</code> في روبي}}</noinclude>
 [[تصنيف: Ruby]]
 [[تصنيف: Ruby Method]]
 [[تصنيف: Ruby Range]]
-باستخدام خوارزمية البحث الثنائي (binary search)، يبحث التابع <code>bsearch</code> عن قيمة من المجال تفي بالشرط المعطى في مدة O (log n) ‎، حيث n يمثل حجم المجال.
+يبحث التابع <code>bsearch</code> باستخدام خوارزمية البحث الثنائي (binary search) عن قيمة من المجال تحقق الشرط المعطى في مدة<code>O (log n)</code> ‎، إذ <code>n</code> يمثل حجم المجال.
+==البنية العامة==
-يمكنك استخدام هذا التابع بطريقتين: وضع البحث الأدنى (find-minimum mode)، أو وضع البحث العادي (find-any mode).  وفي كلتا الحالتين، يجب أن تكون عناصر المجال مُرتبة (sorted) لأجل الكتلة.
+<syntaxhighlight lang="ruby">bsearch {|obj| block }  → value‎</syntaxhighlight>يمكنك استخدام هذا التابع بطريقتين: وضع البحث الأدنى (find-minimum mode)، أو وضع البحث العادي (find-any mode). وفي كلتا الحالتين، يجب أن تكون عناصر المجال مُرتبة (sorted) لأجل الكتلة.
 في وضع البحث الأدنى (يعد هذا خيارًا جيدًا في الحالات العادية)، يجب أن تُعيد الكتلة إما <code>true</code> أو <code>false</code>، ويجب أن تكون هناك قيمة <code>x</code> بحيث:
-* تعيد الكتلة القيمة <code>false</code> لكل القيم الأصغر من <code>x</code>،
+* تعيد الكتلة القيمة <code>false</code> لكل القيم الأصغر من <code>x</code>، و
-* تعيد <code>true</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]
+إن كان <code>x</code> مُتضمنًا في المجال، فسيعيد التابع القيمة <code>x</code>. خلا ذلك، فسيعيد صفرًا.
-(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) بحيث:
+في وضع البحث العادي (سلوكه يشبه سلوك <code>bsearch(3)‎</code>)، يجب أن تعيد الكتلة عددًا، ويجب أن تكون هناك قيمتان <code>x</code> و <code>y</code> (تحققان <code>x <= y</code>) بحيث:
-* تعيد الكتلة عددًا موجبًا لكل v بحيث v <x،
+* تعيد الكتلة عددًا موجبًا لكل <code>v</code> بحيث <code>v < x</code>، و
-* تعيد الكتلة الصفر لـكل v يحقق x <= v <y،
+* تعيد الكتلة الصفر لكل <code>v</code> يحقق <code>x <= v < y</code>، و
-* تعيد الكتلة عددًا سالبًا لكل v يحقق y <= v.
+* تعيد الكتلة عددًا سالبًا لكل <code>v</code> يحقق <code>y <= v</code>.
-يعيد هذا التابع أي قيمة ضمن تقاطع المجال المحدد و <code>x… y</code> (إن وجدت).  إن لم تكن هناك أي قيمة تحقق هذا الشرط، فستُعاد <code>nil</code>.
+يعيد هذا التابع أي قيمة ضمن تقاطع المجال المحدد و <code>x…y</code> (إن وجدت). إن لم تكن هناك أية قيمة تحقق هذا الشرط، فستُعاد القيمة <code>nil</code>.
 يجب عدم خلط الوضعين في وقت واحد؛ يجب أن تعيد الكتلة دائمًا إما <code>true</code> أو <code>false</code>، أو تعيد دائمًا عددًا.
 لا يمكن معرفة القيمة المُلتقطة في كل عملية تكرار (iteration).
-==البنية العامة==
-<syntaxhighlight lang="ruby">bsearch {|obj| block }  → value‎</syntaxhighlight>‎
+== ‎القيمة المعادة ==
-==القيمة المُعادة==
+تعاد إمَّا القيمة <code>true</code> أو القيمة <code>false</code> إن استُعمل وضع البحث الأدنى، أو تعاد قيمة عددية أو القيمة <code>nil</code> إن استعمل وضع البحث العادي (اطلع على قسم البينة العامة لمزيد من التفاصيل).
 ==أمثلة==
+مثال على استخدام التابع <code>bsearch‎</code> في وضع البحث الأدنى:<syntaxhighlight lang="ruby">ary = [0, 4, 7, 10, 12]
-=== مثال على استخدام التابع <code>bsearch‎</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>
+(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]
-=== مثال على استخدام التابع <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/cover-3F|cover?‎]]</code>: يعيد  القيمة <code>true</code> إن كان <code>obj</code> محصورًا بين بداية ونهاية المجال.
+* التابع <code>[[Ruby/Range/cover-3F|cover?‎]]</code>: يتحقق إن كان الكائن المُمرَّر إليه محصورًا بين بداية ونهاية المجال.
 ==مصادر==
-*[http://ruby-doc.org/core-2.5.1/Range.html#method-i-bsearch قسم  التابع bsearch‎ في الصنف Range‎ في توثيق روبي الرسمي.]
+*[http://ruby-doc.org/core-2.5.1/Range.html#method-i-bsearch قسم التابع bsearch‎ في الصنف Range‎ في توثيق روبي الرسمي.]