أين يمكنني الحصول على "مفيدة" C++ البحث الثنائية الخوارزمية ؟

Question

أحتاج الثنائية خوارزمية البحث متوافق مع C++ المحكمة الحاويات ، شيء من هذا القبيل std::binary_search في مستوى المكتبة <algorithm> رأس, ولكن أنا بحاجة للعودة إلى التكرار أن نقطة عند النتيجة ليست بسيطة منطقية تقول لي إذا كان العنصر موجود.

(على الجانب علما, ماذا كان مستوى لجنة التفكير عندما عرف API binary_search?!)

قلقي الرئيسي هنا هو أن كنت في حاجة إلى سرعة البحث الثنائية ، حتى على الرغم من أنني يمكن أن تجد البيانات مع خوارزميات أخرى ، كما هو مذكور أدناه ، أريد أن الاستفادة من حقيقة أن بلدي فرز البيانات للحصول على فوائد البحث الثنائية ، وليس البحث الخطي.

حتى الآن lower_bound و upper_bound تفشل إذا مسند مفقود:

//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

ملاحظة: أنا أيضا بخير باستخدام خوارزمية التي لا تنتمي إلى مساحة الأمراض المنقولة جنسيا طالما لها متوافقة مع الحاويات.مثل القول ، boost::binary_search.

Answer 1

لا توجد مثل هذه الوظائف ، ولكن يمكنك كتابة واحدة بسيطة باستخدام std::lower_bound, std::upper_bound أو std::equal_range.

تطبيق بسيط يمكن

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}

آخر حل هو استخدام std::set, الذي يضمن ترتيب العناصر و يوفر طريقة iterator find(T key) أن يعود مكرر على بند معين.ولكن الاحتياجات الخاصة بك قد لا تكون متوافقة مع استخدام مجموعة (على سبيل المثال إذا كنت بحاجة لتخزين نفس العنصر عدة مرات).

Answer 2

يجب أن يكون لديك نظرة على std::equal_range.فإنه سيعود زوج من التكرار إلى مجموعة من النتائج.

Answer 3

هناك مجموعة منها:

http://www.sgi.com/tech/stl/table_of_contents.html

البحث عن:

• lower_bound
• upper_bound
• equal_range
• binary_search

على صعيد منفصل:

ربما كانوا يفكرون أن البحث الحاويات الأجل أكثر من نتيجة واحدة.ولكن على الغريب المناسبة حيث تحتاج فقط إلى اختبار وجود الإصدار الأمثل من شأنه أيضا أن يكون لطيفا.

Answer 4

إذا std::lower_bound جدا على مستوى منخفض ترضيك ، قد ترغب في التحقق دفعة::الحاوية::flat_multiset.بل هو قطرة في استبدال std::مولتيست يتم فرز ناقلات باستخدام البحث الثنائية.

Answer 5

الأمراض المنقولة جنسيا::lower_bound() :)

Answer 6

تحقق من هذه الوظيفة ، qBinaryFind:

RandomAccessIterator qBinaryFind ( RandomAccessIterator begin, RandomAccessIterator end, const T & value )

يؤدي البحث الثنائية من مجموعة [begin, end) وإرجاع الموقف من حدوث القيمة.إذا كان هناك لا توجد أحداث من قيمة العوائد الغاية.

العناصر في مجموعة [begin, end) يجب أن يتم فرز في ترتيب تصاعدي;انظر qSort().

إذا كان هناك العديد من الحوادث من نفس القيمة ، أي واحد منهم يمكن أن يكون عاد.استخدام qLowerBound() أو qUpperBound() إذا كنت بحاجة إلى أدق التحكم.

على سبيل المثال:

QVector<int> vect;
 vect << 3 << 3 << 6 << 6 << 6 << 8;

 QVector<int>::iterator i =
         qBinaryFind(vect.begin(), vect.end(), 6);
 // i == vect.begin() + 2 (or 3 or 4)

وظيفة مدرجة في <QtAlgorithms> رأس الذي هو جزء من Qt المكتبة.

Answer 7

أقصر تنفيذ متسائلا لماذا لا تدرج في المكتبة القياسية:

template<class ForwardIt, class T, class Compare=std::less<>>
ForwardIt binary_find(ForwardIt first, ForwardIt last, const T& value, Compare comp={})
{
    // Note: BOTH type T and the type after ForwardIt is dereferenced 
    // must be implicitly convertible to BOTH Type1 and Type2, used in Compare. 
    // This is stricter than lower_bound requirement (see above)

    first = std::lower_bound(first, last, value, comp);
    return first != last && !comp(value, *first) ? first : last;
}

من https://en.cppreference.com/w/cpp/algorithm/lower_bound

Answer 8

الحل العودة الموقف داخل النطاق يمكن أن يكون مثل هذا ، فقط باستخدام العمليات على التكرار (يجب أن تعمل حتى لو مكرر لا الحسابي):

template <class InputIterator, typename T>
size_t BinarySearchPos(InputIterator first, InputIterator last, const T& val)
{       
    const InputIterator beginIt = first;
    InputIterator element = first;
    size_t p = 0;
    size_t shift = 0;
    while((first <= last)) 
    {
        p = std::distance(beginIt, first);
        size_t u = std::distance(beginIt, last);
        size_t m = (p+u)/2;
        std::advance(element, m - shift);
        shift = m;
        if(*element == val) 
            return m; // value found at position  m
        if(val > *element)
            first = element++;
        else
            last  = element--;

    }
    // if you are here the value is not present in the list, 
    // however if there are the value should be at position u
    // (here p==u)
    return p;

}

Answer 9

int BinarySearch(vector<int> array,int var)
{ 
    //array should be sorted in ascending order in this case  
    int start=0;
    int end=array.size()-1;
    while(start<=end){
        int mid=(start+end)/2;
        if(array[mid]==var){
            return mid;
        }
        else if(var<array[mid]){
            end=mid-1;
        }
        else{
            start=mid+1;
        }
    }
    return 0;
}

على سبيل المثال:النظر في مجموعة ، A=[1,2,3,4,5,6,7,8,9] لنفترض أنك تريد البحث في الفهرس 3 في البداية start=0 end=9-1=8 الآن منذ بدء<=الغاية ؛ mid=4;(مجموعة[متوسط] وهو 5) !=3 الآن, 3 تقع إلى اليسار من منتصف باعتبارها أصغر من 5.ولذلك ، فإننا البحث فقط الجزء الأيسر من مجموعة ومن هنا تبدأ الآن=0 end=3;متوسط=2.منذ مجموعة[متوسط]==3, ومن ثم لدينا عدد كنا نبحث عن.ومن ثم نعود مؤشره الذي يساوي متوسط.