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

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