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

مراجعة 12:11، 5 سبتمبر 2018

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

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

في وضع البحث عن الحد الأدنى (يعدُّ هذا خيارًا جيدًا لحالات الاستخدام الاعتياديَّة)، يجب أن تعيد الكتلة البرمجية القيمة true أو القيمة false دومًا وأن يكون هناك فهرس i معطى‎‎‎‎ (يتراوح بين ‎0 <= i <= ary.size‎ ‎) وبذلك:

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

يعيد التابع في هذه الحالة العنصر ذو الفهرس i، أو القيمة nil إذا كان i يساوي ary. size.

 ary = [0, 4, 7, 10, 12]
ary.bsearch {|x| x >=   4 } #=> 4
ary.bsearch {|x| x >=   6 } #=> 7
ary.bsearch {|x| x >=  -1 } #=> 0
ary.bsearch {|x| x >= 100 } #=> nil

في وضع البحث العام، يجب أن تعيد الكتلة البرمجية عددًا دومًا، ويجب أن يكون هناك فهرسان i‎ و j‎‎‎ (إذ يكون 0‎ <= i <= j <= ary.size)، وبذلك:

تعيد الكتلة عددًا موجبًا للمصفوفة ary إن كان 0‎ <= k ‎< i‎‎، و
تعيد الكتلة القيمة 0 للمصفوفة ary إن كان i <= k < j، و
تعيد الكتلة عددًا سالبًا للمصفوفة ary إن كان j <= k < ary.size.

في هذه الحالة، يعيد هذا التابع أي عنصر يقع فهرسه بين i‎ و j‎‎‎. إن كانت قيمة i مساويةً لقيمة j (مثل عدم وجود عنصر يحقِّق الكتلة البرمجية)، فسيعيد التابع bsearch حينئذٍ القيمة nil.

أمثلة:

 ary = [0, 4, 7, 10, 12]
# try to find v such that 4 <= v < 8
ary.bsearch {|x| 1 - x / 4 } #=> 4 or 7
# try to find v such that 8 <= v < 10
ary.bsearch {|x| 4 - x / 2 } #=> nil

لا يجب أن تخلط بين الوضعين، إذ ينبغي أن تعيد الكتلة إمَّا القيمة true أو القيمة false دومًا، أو تعيد عددًا دومًا. ولا يمكن معرفة القيمة التي تم اختيارها عند كل تكرار (iteration).

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

 bsearch {|x| block } → elem

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

يعاد أول عنصر يحقق الشرط المحدد في الكتلة block من المصفوفة المعطاة، أو القيمة nil إن لم يكن هنالك أي عنصر متطابق مع الشرط المعطى.

انظر أيضًا

التابع bsearch_index: يبحث باستخدام البحث الثنائي (binary search) عن فهرسٍ لعنصر من مصفوفة يحقق شرطًا منطقيًّا محددًا ويستغرق ‎O(log n)‎، إذ n هي حجم المصفوفة.
التابع assoc: يبحث في العناصر الأولى للمصفوفات الفرعية الموجودة في المصفوفة المستدعاة معه عن الكائن المُمرّر إليها ثم يعيد المصفوفة الفرعية الأولى التي يكون أول عنصر فيها هو ذلك الكائن، أو يعيد القيمة nil في حالة عدم العثور على ذلك الكائن.

مصادر

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

@@ سطر 3: / سطر 3: @@
 [[تصنيف: Ruby Method]]
 [[تصنيف: Ruby Array]]
-يبحث التابع <code>bsearch</code> باستخدام البحث الثنائي (<code>binary</code> <code>search</code>) عن قيمة من مصفوفة تحقق شرطًا منطقيًّا محددًا ويستغرق ‎<code>O</code>(<code>log</code> <code>n</code>)‎، إذ <code>n</code> حجم المصفوفة.
+يبحث التابع <code>bsearch</code> باستخدام البحث الثنائي (binary search) عن قيمة من مصفوفة تحقق شرطًا منطقيًّا محددًا ويستغرق ‎O(log n)‎، إذ <code>n</code> حجم المصفوفة.
-يوجد وضعين لاستعمال هذا التابع هما: وضع البحث عن الحد الأدنى (<code>find</code>-<code>minimum</code> <code>mode</code>)، ووضع البحث العام (<code>find</code>-[[Ruby/Array/any | <code>any</code>]] <code>mode</code>). في كلتا الحالتين، يجب أن تكون عناصر المصفوفة مرتبةً بالتوافق مع الكتلة البرمجية المحدَّدة.
-في وضع البحث عن الحد الأدنى (يعدُّ هذا خيارًا جيدًا لحالات الاستخدام الاعتياديَّة)، يجب أن تعيد الكتلة البرمجية القيمة <code>true</code> أو القيمة <code>false</code> دومًا وأن يكون هناك فهرس <code>i</code> معطى‎‎‎‎ (يتراوح بين ‎0 <= <code>i</code> <= <code>ary</code>.[[Ruby/Array/size | <code>size</code>]]‎ ‎) وبذلك:
+يوجد وضعان لاستعمال هذا التابع هما: وضع البحث عن الحد الأدنى (find-minimum mode)، ووضع البحث العام (find- any mode). في كلتا الحالتين، يجب أن تكون عناصر المصفوفة مرتبةً بالتوافق مع الكتلة البرمجية المحدَّدة.
+في وضع البحث عن الحد الأدنى (يعدُّ هذا خيارًا جيدًا لحالات الاستخدام الاعتياديَّة)، يجب أن تعيد الكتلة البرمجية القيمة <code>true</code> أو القيمة <code>false</code> دومًا وأن يكون هناك فهرس <code>i</code> معطى‎‎‎‎ (يتراوح بين ‎<code>0</code> <code><= i <= ary.size</code>‎ ‎) وبذلك:
 * تعيد الكتلة القيمة <code>false</code> لأي عنصر فهرسه أصغر من <code>i</code>، و
 * تعيد الكتلة القيمة <code>true</code> لأي عنصر فهرسه أكبر من أو يساوي <code>i</code>.
 يعيد التابع في هذه الحالة العنصر ذو الفهرس <code>i</code>، أو القيمة <code>nil</code> إذا كان <code>i</code> يساوي <code>ary</code>.[[Ruby/Array/size | <code>size</code>]].
-<code>ary</code> = [0, 4, 7, 10, 12]
+<syntaxhighlight lang="ruby"> ary = [0, 4, 7, 10, 12]
-<code>ary</code>.<code>bsearch</code> {|<code>x</code>| <code>x</code> >=   4 } #=> 4
+ary.bsearch {|x| x >=   4 } #=> 4
-<code>ary</code>.<code>bsearch</code> {|<code>x</code>| <code>x</code> >=   6 } #=> 7
+ary.bsearch {|x| x >=   6 } #=> 7
-<code>ary</code>.<code>bsearch</code> {|<code>x</code>| <code>x</code> >=  -1 } #=> 0
+ary.bsearch {|x| x >=  -1 } #=> 0
-<code>ary</code>.<code>bsearch</code> {|<code>x</code>| <code>x</code> >= 100 } #=> <code>nil</code>
+ary.bsearch {|x| x >= 100 } #=> nil </syntaxhighlight>
-في وضع البحث العام، يجب أن تعيد الكتلة البرمجية عددًا دومًا، ويجب أن يكون هناك فهرسان <code>i</code>‎ و <code>j</code>‎‎‎ (إذ يكون 0‎ <= <code>i</code> <= <code>j</code> <= <code>ary</code>.[[Ruby/Array/size | <code>size</code>]])، وبذلك:
+في وضع البحث العام، يجب أن تعيد الكتلة البرمجية عددًا دومًا، ويجب أن يكون هناك فهرسان <code>i</code>‎ و <code>j</code>‎‎‎ (إذ يكون <code>0‎ <= i <= j <= ary.size</code>)، وبذلك:
 * تعيد الكتلة عددًا موجبًا للمصفوفة <code>ary</code> إن كان 0‎ <= <code>k</code> ‎< <code>i</code>‎‎، و
 * تعيد الكتلة القيمة 0 للمصفوفة <code>ary</code> إن كان <code>i</code> <= <code>k</code> < <code>j</code>، و
-* تعيد الكتلة عددًا سالبًا للمصفوفة <code>ary</code> إن كان <code>j</code> <= <code>k</code> < <code>ary</code>.[[Ruby/Array/size | <code>size</code>]].
+* تعيد الكتلة عددًا سالبًا للمصفوفة <code>ary</code> إن كان <code>j</code> <= <code>k</code> < <code>ary</code>.<code>size</code>.
 في هذه الحالة، يعيد هذا التابع أي عنصر يقع فهرسه بين  <code>i</code>‎ و <code>j</code>‎‎‎. إن كانت قيمة <code>i</code> مساويةً لقيمة <code>j</code> (مثل عدم وجود عنصر يحقِّق الكتلة البرمجية)، فسيعيد التابع <code>bsearch</code> حينئذٍ القيمة <code>nil</code>.
 أمثلة:
-<code>ary</code> = [0, 4, 7, 10, 12]
+<syntaxhighlight lang="ruby"> ary = [0, 4, 7, 10, 12]
-# <code>try</code> <code>to</code> <code>find</code> <code>v</code> <code>such</code> <code>that</code> 4 <= <code>v</code> < 8
+# try to find v such that 4 <= v < 8
-<code>ary</code>.<code>bsearch</code> {|<code>x</code>| 1 - <code>x</code> / 4 } #=> 4 <code>or</code> 7
+ary.bsearch {|x| 1 - x / 4 } #=> 4 or 7
-# <code>try</code> <code>to</code> <code>find</code> <code>v</code> <code>such</code> <code>that</code> 8 <= <code>v</code> < 10
+# try to find v such that 8 <= v < 10
-<code>ary</code>.<code>bsearch</code> {|<code>x</code>| 4 - <code>x</code> / 2 } #=> <code>nil</code>
+ary.bsearch {|x| 4 - x / 2 } #=> nil </syntaxhighlight>
-لا يجب أن تخلط بين الوضعين، إذ ينبغي أن تعيد الكتلة إمَّا القيمة <code>true</code> أو القيمة <code>false</code> دومًا، أو تعيد عددًا دومًا. ولا يمكن معرفة القيمة التي تم اختيارها عند كل تكرار (<code>iteration</code>).
+لا يجب أن تخلط بين الوضعين، إذ ينبغي أن تعيد الكتلة إمَّا القيمة <code>true</code> أو القيمة <code>false</code> دومًا، أو تعيد عددًا دومًا. ولا يمكن معرفة القيمة التي تم اختيارها عند كل تكرار (iteration).
 ==البنية العامة==
 <syntaxhighlight lang="ruby"> bsearch {|x| block } → elem
@@ سطر 32: / سطر 35: @@
 يعاد أول عنصر يحقق الشرط المحدد في الكتلة <code>block</code> من المصفوفة المعطاة، أو القيمة <code>nil</code> إن لم يكن هنالك أي عنصر متطابق مع الشرط المعطى.
 ==انظر أيضًا==
-* التابع [[Ruby/Array/bsearch_index | <code>bsearch_index</code>]]: يبحث باستخدام البحث الثنائي (<code>binary</code> <code>search</code>) عن فهرسٍ لعنصر من مصفوفة يحقق شرطًا منطقيًّا محددًا ويستغرق ‎<code>O</code>(<code>log</code> <code>n</code>)‎، إذ <code>n</code> هي حجم المصفوفة.
+* التابع [[Ruby/Array/bsearch_index | <code>bsearch_index</code>]]: يبحث باستخدام البحث الثنائي (binary search) عن فهرسٍ لعنصر من مصفوفة يحقق شرطًا منطقيًّا محددًا ويستغرق ‎<code>O</code>(<code>log</code> <code>n</code>)‎، إذ <code>n</code> هي حجم المصفوفة.
 * التابع [[Ruby/Array/assoc | <code>assoc</code>]]: يبحث في العناصر الأولى للمصفوفات الفرعية الموجودة في المصفوفة المستدعاة معه عن الكائن المُمرّر إليها ثم يعيد المصفوفة الفرعية الأولى التي يكون أول عنصر فيها هو ذلك الكائن، أو يعيد القيمة <code>nil</code> في حالة عدم العثور على ذلك الكائن.
 ==مصادر==
-* قسم التابع bsearch في الصنف Array في توثيق روبي الرسمي.
+* [https://ruby-doc.org/core-2.5.1/Array.html#method-i-bsearch قسم التابع bsearch في الصنف Array في توثيق روبي الرسمي.]