objective-c - 在排序的 NSArray 中查找 NSDate

Question

我有一个 NSDate 对象的排序数组。我想做的是创建一个方法，该方法接受一个日期并根据是否可以在日期数组中找到该日期返回 YES 或 NO。

NSArray *dateArray;

-(BOOL)arrayContainsDate(NSDate *)d {
  // return YES if d is found in dateArray
}

我知道如何通过一个一个地遍历数组的每个元素来做到这一点，但我需要一种更快的方法。

Answer 1

When determining whether an object exists in a set of objects, consider using an NSSet/NSMutableSet object (or NSOrderedSet/NSMutableOrderedSet if you are developing for Mac OS X 10.7 or iOS 5.0 and want to retain the order of elements in the set). An NSSet container is designed for efficient lookups. When an object has a decent hash (which most Foundation objects do), the lookup is effectively O(1), which is faster than a binary search.

NSSet *dateSet = [NSSet setWithArray:dateArray];

if ([dateSet containsObject:date1])
{
    // do something
}

Note that it is important to construct the set once rather than converting it from an array each time, or else you'll lose any performance benefit.

For more information, see here.

---

Since you are wanting to check for specified dates regardless of time, you need to truncate the date values before adding them to the set. For example (pick better names, this is only an example):

// potentially add as a category method to NSDate

- (NSDate *) dateByTruncatingTime
{
    NSDateComponents *components = [[NSCalendar currentCalendar] components:NSYearCalendarUnit|NSMonthCalendarUnit|NSDayCalendarUnit fromDate:aDate];
    return [[NSCalendar currentCalendar] dateFromComponents:components];
}

// ------------- somewhere else -------------

- (void) actionHappened
{
    [myMutableSet addObject:[[NSDate date] dateByTruncatingTime]];
}

- (BOOL) didActionHappenOnDate:(NSDate *) aDate
{
    return [myMutableSet containsObject:[aDate dateByTruncatingTime]];
}

Answer 2

由于您的数组已排序，请使用二分搜索。首先将您的日期与数组的中间元素进行比较（使用compare:） - 如果相等，您就找到了。如果它小于或大于，则重复考虑数组的前半部分或后半部分。等等。

您可以通过使用两个索引来做到这一点 - 您正在考虑的范围的最小值和最大值。计算中间指数，进行比较，然后您要考虑的新范围是 min，middle-1 或 middle+1，max。

这个算法是 O(log2 N) - 你不会做得更好。

代码留作练习！

高温高压

Answer 3

你可以使用哈希。

NSDictionary *dict = {[NSString stringWithFormat:@"%@",date1]:@"",[NSString stringWithFormat:@"%@",date2]:@""}

- (BOOL) containsDate:(NSDate*)_d
{
   return [dict valueForKey:[NSString stringWithFormat:@"%@",_d]] != nil;
}