क्या रूबी में अंतर्निहित बाइनरी-सर्च है?

Question

मैं एक अंतर्निहित रूबी विधि की तलाश में हूं जिसमें index जैसी कार्यक्षमता है लेकिन बाइनरी खोज एल्गोरिदम का उपयोग करता है, और इस प्रकार एक पूर्व-क्रमबद्ध सरणी की आवश्यकता होती है।

मुझे पता है कि मैं अपना खुद का कार्यान्वयन लिख सकता हूं, लेकिन "Ruby#index Method VS Binary Search" के अनुसार, इंडेक्स द्वारा उपयोग की गई अंतर्निहित सरल पुनरावृत्ति खोज बाइनरी खोज के शुद्ध-रूबी संस्करण से तेज है, क्योंकि अंतर्निहित विधि लिखी गई है सी

क्या रूबी बाइनरी खोज करने वाली किसी भी अंतर्निहित विधियों को प्रदान करता है?

Answer 1

रूबी 2.0 ने Array#bsearch और Range#bsearch पेश किया।

रूबी 1.9 के लिए, आपको bsearch और binary_search रत्नों में देखना चाहिए। अन्य संभावना तरह using rbtree

bsearch एक सरणी से एक अलग संग्रह का उपयोग करने के, मेरे backports gem में है, लेकिन यह एक शुद्ध रूबी संस्करण है, इसलिए काफ़ी धीमी। ध्यान दें कि एक शुद्ध रूबी बाइनरी खोज अभी भी index या include? की तुलना में एक रैखिक बिल्टिन खोज की तुलना में तेज़ पर्याप्त सरणी/श्रेणियों (या महंगे तुलना) के लिए तेज होगी, क्योंकि यह O(log n) बनाम O(n) बनाम जटिलता का एक ही क्रम नहीं है।

आज इसके साथ खेलने के लिए, आप require 'backports/2.0.0/array/bsearch' या require 'backports/2.0.0/range/bsearch' कर सकते हैं।

शुभकामनाएं!

Answer 2

एक बहुत 2011 के बाद से बदल गया है, रूबी 2.3 में, आप bsearch_index

https://ruby-doc.org/core-2.3.0/Array.html#method-i-bsearch_index

array.bsearch_index { |val| query <=> val }