लुकअप टेबल में निकटतम मूल्य की खोज कैसे करें?

Question

मेरे पास पूर्णांक मानों का एक सरल आयामी सरणी है जो भाग मूल्यों के भौतिक सेट का प्रतिनिधित्व करती है जिनके साथ मुझे काम करना है। मैं फिर गणितीय रूप से गणना और आदर्श मूल्य।

मैं एक कुशल खोज एल्गोरिदम कैसे लिख सकता हूं जो सरणी में मेरे आदर्श मूल्य से सबसे छोटा abosulte अंतर मिलेगा?

सरणी पूर्वनिर्धारित और स्थिर है, इसलिए इसे क्रमबद्ध किया जा सकता है हालांकि मुझे आवश्यकता है।

उदाहरण लुक सरणी:

100, 152, 256, 282, 300 

125 का एक आदर्श मूल्य के लिए सर्च कर रहे हैं सरणी में 100 मिलेगा, जबकि 127 मिलेगा 152.

वास्तविक देखने सरणी लगभग 250 आइटम लंबा होगा और कभी नहीं बदलते हैं।

Answer 1

एक बार सरणी सॉर्ट हो जाता है, binary search

Answer 2

बस सरणी और कंप्यूटिंग पेट के माध्यम से जा रहा है (संदर्भ-array_value [i]) ओ (एन) ले जाएगा। सूचकांक को सबसे छोटे अंतर के साथ ले जाएं।

Answer 3

अजगर, अवर्गीकृत सूची पर जानवर बल का उपयोग (यह कारण मज़ा लेखन अजगर) O(n):

table = (100, 152, 256, 282, 300) 
value = 125 

lookup_dict = dict([(abs(value-x),x) for x in table]) 
closest_val = ldict[min(ldict.keys())] 

और एक उचित कार्यान्वयन मूल्य खोजने के लिए द्विआधारी खोज का उपयोग करता है O(log_n):

import bisect 
'''Returns the closest entry in the sorted list 'sorted' to 'value' 
''' 
def find_closest(sorted, value): 
    if (value <= sorted[0]): 
     return sorted[0] 
    if (value >= sorted[-1]): 
     return sorted[-1] 
    insertpos = bisect.bisect(sorted, value) 
    if (abs(sorted[insertpos-1] - value) <= abs(sorted[insertpos] - value)): 
     return sorted[insertpos-1] 
    else: 
     return sorted[insertpos] 

Answer 4

यह बहुत छोड़कर अगर यह सही कुंजी नहीं मिल रहा है एक द्विआधारी खोज के समान है, यह होगा आर एक कुंजी प्रदान करें कुंजी प्रदान की कुंजी के बहुत करीब होगा।

तर्क तब तक खोजना है जब तक सटीक कुंजी नहीं मिलती है या जब तक बाइनरी खोज करते समय उच्च कुंजी और निम्न के बीच बिल्कुल एक कुंजी शेष नहीं होती है।

एक सरणी पर विचार करें n [] = {1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20}
अगर आप कुंजी के लिए खोज: 2 तो वह एल्गोरिथ्म, नीचे का उपयोग कर
चरण 1: उच्च = 10, कम = 0, मेड = 5
चरण 2: उच्च = 5, कम = 0, मेड = 2
चरण 3: उच्च = 2, कम = 0, med = 1 इसमें सही कुंजी पाएं कदम। तो यह रिटर्न 1.

यदि आप के लिए महत्वपूर्ण खोज: 3 (जो सरणी में मौजूद नहीं है), तो नीचे दिए गए एल्गोरिथ्म
चरण 1 का उपयोग कर: उच्च = 10, कम = 0, मेड = 5
चरण 2: उच्च = 5, कम = 0, मेड = 2
चरण 3: उच्च = 2, कम = 0, मेड = 1
चरण 4: उच्च = 1, कम = 0, इस चरण में उच्च = कम + 1 यानी खोज करने के लिए कोई और तत्व नहीं है। तो यह med = 1 देता है।

आशा है कि इससे मदद मिलती है ...

public static <T> int binarySearch(List<T> list, T key, Comparator<T> compare) { 
       int low, high, med, c; 
       T temp; 
       high = list.size(); 
       low = 0; 
       med = (high + low)/2; 

       while (high != low+1) { 
        temp = list.get(med); 
        c = compare.compare(temp, key); 

        if (c == 0) { 
         return med; 
        } else if (c < 0){ 
         low = med; 
        }else{ 
         high = med; 
        } 

        med = (high + low)/2; 
       } 

       return med; 
      } 

    /** ------------------------ Example -------------------- **/ 

    public static void main(String[] args) { 
       List<Integer> nos = new ArrayList<Integer>(); 
       nos.addAll(Arrays.asList(new Integer[]{1, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20})); 

       search(nos, 2); // Output Search:2 Key:1 Value:2 
       search(nos, 3); // Output Search:3 Key:1 Value:2 

       search(nos, 10); // Output Search:10 Key:5 Value:10 
       search(nos, 11); // Output Search:11 Key:5 Value:10 
      } 

    public static void search(List<Integer> nos, int search){ 
       int key = binarySearch(nos, search, new IntComparator()); 
       System.out.println("Search:"+search+"\tKey:"+key+"\tValue:"+nos.get(key)); 
      } 

      public static class IntComparator implements Comparator<Integer>{ 
       @Override 
       public int compare(Integer o1, Integer o2) { 
        return o1.compareTo(o2); 
       } 
      } 

Answer 5

विकिपीडिया से द्विआधारी खोज एल्गोरिथ्म के रूप में नीचे है:

int binary_search(int A[], int key, int imin, int imax) 
{ 
    // continue searching while [imin,imax] is not empty 
    while (imax >= imin) 
    { 
     // calculate the midpoint for roughly equal partition 
     int imid = midpoint(imin, imax); 
     if(A[imid] == key) 
     // key found at index imid 
     return imid; 
     // determine which subarray to search 
     else if (A[imid] < key) 
     // change min index to search upper subarray 
     imin = imid + 1; 
     else   
     // change max index to search lower subarray 
     imax = imid - 1; 
    } 
    // key was not found 
    return KEY_NOT_FOUND; 
} 

अंत हालत मामले में एक महत्वपूर्ण नहीं मिला है कि imax < imin है।

वास्तव में, यह स्थिति निकटतम मैच का पता लगा सकती है। निकटतम मैच imax और imin के बीच होगा (खाते में लेना सरणी सीमाओं के बाहर हो सकता है)। अंत मामले में imax < imin फिर से ध्यान दें। कुछ समाधान पेट का उपयोग अंतर को खोजने के लिए, लेकिन हम उस A[imax] < key < A[imin] इतना पता है:

if imax <= 0 return 0 
if imin >= A.count - 1 return A.count - 1 
if (key - A[imax]) < (A[imin] - key) return imax 
return imin