If I understand correctly, you have a list of ordered elements, and a partial match. Binary search will help, but won't be exactly what you want. To do something similar, I use a binary search which does a length restricted string comparison to find an element which matches, and then backs up to find the first match. For my application this approach is fine, since I only have a few items in each such grouping. Your mileage may vary. However, a better approach, which someone has already suggested, might be to have a small array of indices into the array, keyed by first letter. Essentially something like this: typedef struct index { TCHAR chr; int start; } INDEX; CArray<INDEX, INDEX&>> ix; INDEX in; ix.RemoveAll(); in.chr = _T('\0'); in.start = -1; for(i = 0; i < nElements; i++) { // get first char of this item... chr = ....; if (in.chr!=chr) { // make a new index entry in.chr = chr; in.start = i; ix.Add(in); } } in.chr = _T('\0'); in.start = nElements; ix.Add(in); To do your search, look in the ix array for a matching first character, get the start index from the matching entry, and the stop index from the next entry :) This gives you a smaller space to do additional matching if necessary.
Steve S Developer for hire