Search for strings in large array takes a long time

Question

I'm implementing a search field that filters a UITableView according to the text the user enters.
The TableView is built from an array that holds NSStrings (the data to display and search) and may contain 6000+ items.
When the user starts the search, I'm implementing the -(void)searchBar:(UISearchBar *)searchBar textDidChange:(NSString *)searchText method.

My code works, however, when the data array is large, it is very slow and creating a really bad user experience (my iPhone 4s get stuck for a good few seconds).

The way I'm implementing the search (in the method mentioned above) is this:

NSMutableArray *discardedItems = [[NSMutableArray alloc] init]; // Items to be removed
searchResultsArray = [[NSMutableArray alloc] initWithArray:containerArray]; // The array that holds all the data

// Search for matching results
for (int i=0; i<[searchResultsArray count]; i++) {   
    NSString *data = [[containerArray objectAtIndex:i] lowercaseString];
    NSRange r = [data rangeOfString:searchText];
    if (r.location == NSNotFound) {
        // Mark the items to be removed
        [discardedItems addObject:[searchResultsArray objectAtIndex:i]];
    }
}
// update the display array
[searchResultsArray removeObjectsInArray:discardedItems];
[myTableView reloadData];

I did not think that looping over an array with a few thousand items would cause any issue...
Any suggestion will be appreciated!

UPDATE I've just realized that what takes most of the time is this:

[searchResultsArray removeObjectsInArray:discardedItems];

Answer 1

Try fast enumeration way, my snippet:

- (void)searchBar:(UISearchBar*)searchBar textDidChange:(NSString*)text
{
    if(text.length == 0)
    {
        self.isFiltered = NO;
    }
    else
    {
        self.isFiltered = YES;
        self.searchArray = [NSMutableArray arrayWithCapacity:self.places.count];

        for (PTGPlace* place in self.places)
        {
            NSRange nameRange = [place.name rangeOfString:text options:NSCaseInsensitiveSearch];

            if(nameRange.location != NSNotFound)
            {
                [self.searchArray addObject:place];
            }
        }
    }

    [self.tableView reloadData];
}

- (NSInteger)tableView:(UITableView *)tableView numberOfRowsInSection:(NSInteger)section
{
    if(self.isFiltered)
        return self.searchArray.count;
    else
        return self.places.count;
}

In cellForRowAtIndexPath:

    PTGPlace *place = nil;

    if(self.isFiltered)
        place = [self.searchArray objectAtIndex:indexPath.row];
    else
        place = [self.places objectAtIndex:indexPath.row];

    // Configure the cell...
    cell.textLabel.text = place.name;
    cell.detailTextLabel.text = [place subtitle];

Answer 2

Try this:

for the first three positions, create 26 index sets, each representing the array index of items with that letter (just lower case). That is, say a entry at idx=100 starts with "formula". The index set representing "f" in the first position will contain the index "100". The index set for the second character 'o' will contain the index 100, and the index set for the third character 'r' will contain 100.

When the user types the character 'f', you immediately have the index set of all array items starting with 'f' (and can create a subset of your major array quickly). When an 'o' is typed next, you can find the intersection of indexes in the first match with the second match. Ditto for the third. Now make a subarray of the major array that had the first three indexes match - you can just use the index sets for this.

Using this drastically reduced array, you can now do brute force matching as you were doing originally.