التابع Array.bsearch في روبي
يبحث التابع 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في حالة عدم العثور على ذلك الكائن.