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