在排序的NSArray中查找NSDate

Question

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

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

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

Answer 1

在确定一个对象是否存在于一组对象中时，请考虑使用NSSet/NSMutableSet对象（如果您正在为Mac OS X 10.7或iOS 5.0开发，并且希望保留该集中元素的顺序，则可以使用NSOrderedSet/NSMutableOrderedSet）。NSSet容器是为高效查找而设计的。当一个对象有一个不错的hash（大多数Foundation对象都是这样）时，查找实际上是O（1），这比二进制搜索更快。

NSSet *dateSet = [NSSet setWithArray:dateArray];
if ([dateSet containsObject:date1])
{
    // do something
}

请注意，重要的是构造一次集合，而不是每次从数组转换它，否则您将失去任何性能优势。

有关更多信息，请参阅此处。

---

由于您希望在不考虑时间的情况下检查指定的日期，因此在将日期值添加到集合之前，需要截断日期值。例如（选择更好的名称，这只是一个例子）：

// 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

您可以使用hash。

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

Answer 3

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

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

这个算法是O（log2N）-你不会做得更好。

代码只是一个练习！

HTH