पहला तत्व सख्ती से एक वेक्टर आदेश

Question

अवरोही क्रम में सॉर्ट किया मुझे समझ में एक महत्वपूर्ण की तुलना में कम है कि इस कार्य find_if() एसटीएल-एल्गोरिथ्म समारोह का उपयोग कर के रूप में निम्नानुसार पूरा किया जा सकता का पता लगाएं परिणामस्वरूप लॉगरिदमिक समय में प्राप्त किया जा सकता है। चूंकि वेक्टर पहले ही अवरोही क्रम में क्रमबद्ध है, इसलिए मैं एक बाइनरी खोज दृष्टिकोण का उपयोग करना चाहता हूं।

मैं समझता हूं कि एसटीएल एल्गोरिदम फ़ंक्शन lower_bound और upper_bound लॉगरिदमिक जटिलता की गारंटी देता है। हालांकि मैं यह समझने में असमर्थ हूं कि कुंजी के मुकाबले पहले तत्व को प्राप्त करने के लिए इन तत्वों का उपयोग कैसे करें, क्योंकि किसी कुंजी से अधिक या उसके बराबर पहले तत्व के विपरीत।

उदाहरण के लिए:

मान लीजिए मेरी वेक्टर सामग्री हैं: 21 9 8 7 6 4

मेरे कुंजी है: 10

मैं उत्पादन 9 होना चाहता हूँ, क्योंकि एक में अपना पहला तत्व दाएं से बाएं 10 से कम वेक्टर का स्कैन करें।

इस संबंध में कोई भी मदद बहुत उपयोगी होगी!

धन्यवाद

Answer 1

आप कार्यात्मक वस्तु std::greater के साथ मानक एल्गोरिथ्म std::upper_bound उपयोग कर सकते हैं।

यहां एक उदाहरण दिया गया है कि यह कैसे किया जा सकता है।

#include <iostream> 
#include <iterator> 
#include <functional> 
#include <algorithm> 

int main() 
{ 
    int a[] = { 21, 9, 8, 7, 6, 4 }; 
    int key = 10; 

    auto it = std::upper_bound(std::begin(a), std::end(a), 
     key, std::greater<int>()); 

    if (it != std::end(a)) std::cout << *it << std::endl; 
} 

कार्यक्रम उत्पादन

9 

मूल रूप से