One Quickie

---

Binary Searching in a sorted NSArray (NSArray->General)

How do you binary search a sorted NSArray? Use toll free bridging to CFArray which actually has a binary search function:

    NSMutableArray *sortedArray = [NSMutableArray arrayWithObjects: @"Alice", @"Beth", @"Carol",@"Ellen",nil];
    
    //Where is "Beth"?
    unsigned index = (unsigned)CFArrayBSearchValues((CFArrayRef)sortedArray,
                                                    CFRangeMake(0, CFArrayGetCount((CFArrayRef)sortedArray)),
                                                    (CFStringRef)@"Beth",
                                                    (CFComparatorFunction)CFStringCompare,
                                                    NULL);
    if (index < [sortedArray count] && [@"Beth" isEqualToString:[sortedArray[index]])
    {
        NSLog(@"Beth was found at index %u", index);
    } else {
        NSLog(@"Beth was not found (index is beyond the bounds of sortedArray)");
    }
    
    //Where should we insert "Debra"?
    unsigned insertIndex = (unsigned)CFArrayBSearchValues((CFArrayRef)sortedArray,
                                                          CFRangeMake(0, CFArrayGetCount((CFArrayRef)sortedArray)),
                                                          (CFStringRef)@"Debra",
                                                          (CFComparatorFunction)CFStringCompare,
                                                          NULL);
    [sortedArray insertObject:@"Debra" atIndex:insertIndex];
    NSLog([sortedArray description]);

    //note: NSArray indices and counts were typed as unsigned.  With the move to 64-bit, they are NSUInteger.
    //CFArray indices and counts are CFIndex, which was SInt32 but also will move to 64-bit?
    //Why was it ever signed and will it remain so?

Muchos Thankos to James Hober for this one.

Gus Mueller chimed in saying that if you use CFArrayBSearchValues, be sure to sort with CFArraySortValues rather than using the Cocoa sorting routines (or at least the comparison) - they treat diacritic marks differently, leading to strange errors. From Gus, a quick objc addition to NSMutableArray:

- (void) cfStringSort {
   CFArraySortValues((CFMutableArrayRef)self, CFRangeMake(0, [self count]), (CFComparatorFunction)CFStringCompare, NULL);
}

Thanks to Preston Jackson for finding a bug in the original implementation. In the case of "not found", it returns the insertion point to put this item, so if you're interested in "is this thing there", you need to compare to what was found.