search NSArray contains NSDictionary, with "time efficiency"

I know there are lots of question already being asked, however I am throwing one more question to catch. I've an array contains, huge amount (thousands of records) of data in NSDictionary format, I am trying to perform search within a key in dictionaries into array.

I'm performing search in UITextField - (BOOL)textField:(UITextField *)textField shouldChangeCharactersInRange:(NSRange)range replacementString:(NSString *)string; data source method,

My search requirements is within entire strings,

example strings,

aaa, abeb, abcd, abbec like strings

searching flow,

if a return me all strings,

if aa return aaa only,

if ab return abeb, abcd, abbec like,

important, if its cd then only returns abcd

I've tried it using these ways,

Using NSPredicates

NSLog(@"start search at : %@",[NSDate date]);
NSPredicate *predicate = [NSPredicate predicateWithFormat:@"Name contains[cd] %@", matchString];
searchArray = [[meadArray filteredArrayUsingPredicate:predicate] mutableCopy];
NSLog(@"Search found count = %d",searchArray.count);
[tableCheck reloadData];
NSLog(@"End search at : %@",[NSDate date]);

another way - through Iteration,

NSLog(@"start search at : %@",[NSDate date]);
for (NSDictionary *word in arrayNames)
{
    if ([matchString length] == 0)
    {
        [searchArray addObject:word];
        continue;
    }
    NSRange lastRange = [[[word valueForKey:@"Name"] uppercaseString] rangeOfString:upString];

    if ( lastRange.location != NSNotFound)
    {
        if(range.location == 0 || lastRange.location == 0)
        {
            [searchArray addObject:word];
        }
    }
}    
NSLog(@"End search at : %@",[NSDate date]);

Both the methods working fine, and results as I expected, but ONLY IN SIMULATOR! when I test the same in device, its takes around 1 / 2 / 3 seconds as per the search expands, say at first if I type, a it took 3 seconds, for aa it tooks some 2 seconds, and so on. IT LOOKS CLUMSY ON DEVICE, ANY PRESSED KEY WILL BE REMAIN HIGHLIGHTED UNTIL SEARCH NOT DONE.

Is there any way, that I can perform even faster search using the same method I'm using or any other alternatives!

Update 1

Also tried with CFArrayBSearchValues It only returns index for search string, but I want something that returns all strings which match.

unsigned index = (unsigned)CFArrayBSearchValues((CFArrayRef)meadArray, CFRangeMake(0, CFArrayGetCount((CFArrayRef)meadArray)), (CFStringRef)matchString,(CFComparatorFunction)CFStringCompare, NULL);

Update 2

As per the Alladinian comment, I performed search operation in background thread, yes now its not lock UI, but still searching is too slow, What I'm doing is, performing a selector for some delay say 0.25 seconds, also cancelling any previous selector calls, and then performing searching in background, also reloading table in main thread. Its working like, If I type character with some delay, its works good, but if I type whole word at once, it will loading / updating table as per the characters pressed, at last it will show me the actual output, takes 3-4 seconds for showing the actual content.

Any suggestion or help highly appreciated!

This answer is following anktastic answer, I am also adding my answer because someone will directly get a solution for which we made lots of effort :)

- (BOOL)textField:(UITextField *)textField shouldChangeCharactersInRange:(NSRange)range replacementString:(NSString *)string 
{
    //Cancel any previous selector calls
    [NSRunLoop cancelPreviousPerformRequestsWithTarget:self];

        if(string.length > 0)
        {
            NSString *str = [txt1.text substringToIndex:[txt1.text length] - 1];
            //delay is useful in smooth search - if you're performing web service calls for searching on cloud, then you should give delay as per your test
            [self performSelector:@selector(startSearch:) withObject:str afterDelay:0.05f];
        }
    }
}

- (void) startSearch:(NSString *)matchString
{
    //Cancel any previous operation added in queue
    [queue cancelAllOperations];
    //Create new operation
    NSInvocationOperation* operation = [[NSInvocationOperation alloc]initWithTarget:self selector:@selector(search:) object:matchString];
    [queue addOperation:operation];
}

- (void) search:(NSString *)matchString
{
    //Performing search operation
    NSPredicate *predicate = [NSPredicate predicateWithFormat:@"Name contains[cd] %@", matchString];
    searchArray = [[meadArray filteredArrayUsingPredicate:predicate] mutableCopy];
    //only call again after any previous reload done
    [self performSelectorOnMainThread:@selector(reloadInMainThread) withObject:nil waitUntilDone:YES];
}

- (void) reloadInMainThread 
{
    //Reloading table in main thread for instance search effect
    [tableCheck reloadData];
}