एनएसएआरएआरई पर बाइनरी खोज कैसे करें?

Question

एक (पहले से) क्रमबद्ध NSArray पर बाइनरी खोज करने का सबसे आसान तरीका क्या है?

कुछ संभावित तरीकों मैं अब तक देखा है में शामिल हैं:

1. के उपयोग CFArrayBSearchValues (उल्लेख here) - एक NSArray पर यह काम करेंगे?

2. विधि NSArray की indexOfObject:inSortedRange:options:usingComparator: ग्रहण सरणी अनुसार क्रमबद्ध और प्रकार NSBinarySearchingOptions के opts परम लेता है - इसका मतलब यह एक द्विआधारी खोज करता है? docs सिर्फ इतना कहना:

   , सूचकांक किसी निर्दिष्ट सीमा के भीतर एक वस्तु का एक दिया NSComparator ब्लॉक का उपयोग सरणी में तत्वों के साथ तुलना में।

3. अपनी खुद की बाइनरी खोज विधि (this की तर्ज पर कुछ लिखें) लिखें।

मुझे लगता है कि मैं पहले से iOS 4.3+

धन्यवाद के लिए प्रोग्रामिंग कर रहा हूँ जोड़ना चाहिए।

Answer 1

1 और 2 दोनों काम करेंगे। # 2 शायद आसान है; यह निश्चित रूप से उस विधि के लिए बाइनरी खोज के अलावा कुछ भी करने के लिए समझ में नहीं आता है (यदि सीमा एक निश्चित आकार से ऊपर है, तो कहें)। आप एक बड़ी सरणी पर सत्यापित कर सकते हैं कि यह केवल थोड़ी सी तुलना करता है।

Answer 2

CFArrayBSearchValues काम करना चाहिए- NSArray *CFArrayRef के साथ काम करना चाहिए।

Answer 3

दूसरा विकल्प निश्चित रूप से सबसे सरल है। ओले Begemann कैसे NSArray के indexOfObject:inSortedRange:options:usingComparator: विधि का उपयोग करने पर एक ब्लॉग प्रविष्टि है:

NSArray *sortedArray = ... // must be sorted 
id searchObject = ... 
NSRange searchRange = NSMakeRange(0, [sortedArray count]); 
NSUInteger findIndex = [sortedArray indexOfObject:searchObject 
           inSortedRange:searchRange 
             options:NSBinarySearchingFirstEqual 
           usingComparator:^(id obj1, id obj2) 
           { 
            return [obj1 compare:obj2]; 
           }]; 

NSArray Binary Search

Answer 4

मैं हैरान कोई भी NSSet के उपयोग उल्लेख किया है कि कर रहा हूँ देखें कि किन [जब यह एक साथ वस्तुओं में शामिल है सभ्य हैश, जैसे अधिकांश फाउंडेशन डेटा प्रकार] निरंतर समय लुकअप करता है। किसी ऑब्जेक्ट में अपनी ऑब्जेक्ट्स जोड़ने के बजाय, इसके बजाय एक सेट में जोड़ें (या उन्हें दोनों उद्देश्यों के लिए सॉर्ट किए गए ऑर्डर को बनाए रखने की आवश्यकता है [या वैकल्पिक रूप से आईओएस 5.0 या मैक ओएस एक्स 10.7 पर NSOrderedSet])।

निर्धारित करने के लिए एक वस्तु एक सेट में मौजूद है या नहीं:

NSSet *mySet = [NSSet setWithArray:myArray]; // try to do this step only once 

if ([mySet containsObject:someObject]) 
{ 
    // do something 
} 

वैकल्पिक रूप से:

NSSet *mySet = [NSSet setWithArray:myArray]; // try and do this step only once 

id obj = [mySet member:someObject]; 

// obj is now set to nil if the object doesn't exist or it is 
// set to an object that "isEqual:" to someObject (which could be 
// someObject itself). 

यह पता है कि तुम किसी भी प्रदर्शन लाभ खो देंगे अगर आप एक सेट के लिए सरणी परिवर्तित महत्वपूर्ण है प्रत्येक बार जब आप एक लुकअप करते हैं, तो आदर्श रूप से आप एक प्रीकोनस्ट्रक्टेड सेट का उपयोग करेंगे जिसमें वे ऑब्जेक्ट्स शामिल हैं जिन्हें आप परीक्षण करना चाहते हैं।

Answer 5

//Method to pass array and number we are searching for. 
- (void)binarySearch:(NSArray *)array numberToEnter:(NSNumber *)key{ 


    NSUInteger minIndex = 0; 
    NSUInteger maxIndex = array.count-1; 
    NSUInteger midIndex = array.count/2; 


    NSNumber *minIndexValue = array[minIndex]; 
    NSNumber *midIndexValue = array[midIndex]; 
    NSNumber *maxIndexValue = array[maxIndex]; 

    //Check to make sure array is within bounds 
    if (key > maxIndexValue || key < minIndexValue) { 
     NSLog(@"Key is not within Range"); 
     return; 
    } 

    NSLog(@"Mid indexValue is %@", midIndexValue); 

    //If key is less than the middleIndexValue then sliceUpArray and recursively call method again 
    if (key < midIndexValue){ 
     NSArray *slicedArray = [array subarrayWithRange:NSMakeRange(minIndex, array.count/2)]; 
     NSLog(@"Sliced array is %@", slicedArray); 
     [self binarySearch:slicedArray numberToEnter:key]; 

    //If key is greater than the middleIndexValue then sliceUpArray and recursively call method again 
    } else if (key > midIndexValue) { 
     NSArray *slicedArray = [array subarrayWithRange:NSMakeRange(midIndex+1, array.count/2)]; 
     NSLog(@"Sliced array is %@", slicedArray); 
     [self binarySearch:slicedArray numberToEnter:key]; 

    } else { 
     //Else number was found 
     NSLog(@"Number found"); 
    } 

} 


//Call Method 

@interface ViewController() 
@property(nonatomic)NSArray *searchArray; 
@end 


- (void)viewDidLoad { 
    [super viewDidLoad]; 
//Initialize the array with 10 values 
    self.searchArray = @[@1,@2,@3,@4,@5,@6,@7,@8,@9,@10]; 

//Call Method and search for any number 
    [self binarySearch:self.searchArray numberToEnter:@5]; 
    // Do any additional setup after loading the view, typically from a nib. 
}