यह निर्धारित करने का सबसे तेज़ तरीका है कि कोई तत्व सॉर्ट किए गए सरणी

Question

में है या नहीं, मेरे पास 1000 या अधिक मानों के साथ क्रमबद्ध सॉर्ट की एक सरणी है (5000+ तक हो सकती है)। मुझे एक ऐसा फ़ंक्शन लिखना होगा जो एक int प्राप्त करता है और सरणी में मौजूद तत्व के आधार पर एक बूल देता है। मुझे पता है कि मैं ब्रेक के साथ लूप के लिए लिख सकता हूं, मुझे पता है कि मैं jquery का उपयोग कर सकता हूं .अन्रे।

यह लागू करने का सबसे अच्छा तरीका क्या होगा, यह पता चलाना कि सरणी क्रमबद्ध है।

धन्यवाद।

Answer 1

यह जानकर कि सरणी को बाइनरी खोज सॉर्ट किया गया है, वह सबसे अच्छा तरीका होगा।

Answer 2

यदि सरणी सॉर्ट की गई है, तो उत्तर का क्रमबद्ध - बाइनरी काट का उपयोग करें।

Answer 3

मुझे लगता है कि आप एक बाइनरी खोज दिनचर्या का उपयोग करना चाहते हैं। एक द्विआधारी खोज दिनचर्या है जबकि एक रैखिक खोज औसतन है।

फॉर्म चुनने के लिए कई भिन्नताएं हैं। यहाँ एक मैं this article में पाया:

function binarySearch(items, value){ 

    var startIndex = 0, 
     stopIndex = items.length - 1, 
     middle  = Math.floor((stopIndex + startIndex)/2); 

    while(items[middle] != value && startIndex < stopIndex){ 

     //adjust search area 
     if (value < items[middle]){ 
      stopIndex = middle - 1; 
     } else if (value > items[middle]){ 
      startIndex = middle + 1; 
     } 

     //recalculate middle 
     middle = Math.floor((stopIndex + startIndex)/2); 
    } 

    //make sure it's the right value 
    return (items[middle] != value) ? -1 : middle; 
} 

या एक असंख्य अलग अलग भाषाओं में एक द्विआधारी खोज समारोह है कि this article से इस सरल देख संस्करण।

function binary_search_iterative(a, value) { 
    var lo = 0, hi = a.length - 1, mid; 
    while (lo <= hi) { 
     mid = Math.floor((lo+hi)/2); 
     if (a[mid] > value) 
      hi = mid - 1; 
     else if (a[mid] < value) 
      lo = mid + 1; 
     else 
      return mid; 
    } 
    return null; 
} 

वहाँ भी कोड here के साथ गूगल बंद में एक द्विआधारी खोज है।

और, बाइनरी खोज एल्गोरिदम Wikipedia पर कैसे काम करता है इसका एक अच्छा विवरण है।

Answer 4

कई भाषाओं में पहले से ही यह जावा में उदाहरण के लिए लागू किया गया है, आप केवल संग्रह कोलेक्शन। बाइनरीशर्च (सूची> सूची, टी कुंजी) विधि का उपयोग कर सकते हैं और मुझे पूरा यकीन है कि सी # में बाइनरीशर्च विधि का कुछ प्रकार भी है।

Answer 5

यदि एक से अधिक बार लुकअप कर रहे हैं, तो मानचित्र-जैसी वस्तु पर माइग्रेट करें।

var fastLookup = {}; 
 
mySortedArray.forEach(function(i){fastLookup[i]=true)}); 
 

 
//Each time: 
 
    if (fastLookup[key]===true){ //do thing 
 
    }