[-De-]

Если правильно, то за ~0 мс ищет)
Ну и вообще то, что оно находит и правильное название города - разные штуки, можно, например, в вектор, кроме строки засунуть ссылку на правильный город.

var strVector:Vector.<String> = getStringVector(100000);
 
			var startTime:Number = new Date().getTime();
 
			var stringCount:int = strVector.length;
			var matchCount:int = 0;
			var from:int = 0;
			var to:int = stringCount;
			var test:int;
			while (true)
			{
				test = (from + to) / 2;
				var compResult:int = strVector[test].localeCompare("cfd");
				if (compResult == 0)
				{
					matchCount = 3;
					break;
				}
				else {
					if (Math.abs(from - to) == 1) {
						var compFrom:int = Math.abs(strVector[from].substr(0, 3).localeCompare("cfd"));
						var compTo:int = Math.abs(strVector[to].substr(0, 3).localeCompare("cfd"));
						if (compFrom > compTo) {
							test = to;
							matchCount = 3 - compTo;
						}
						else {
							test = from;
							matchCount = 3 - compFrom;
						}
						break;
					}
					if (compResult < 0) {
						from = test;
					}
					else to = test;
				}
				trace(from, to);//вообще неплохо бы убрать для скорости
			}
			trace(matchCount, 'found in :', new Date().getTime() - startTime, "String is ",strVector[test]);
 
 
 
			function compare(v1:String, v2:String):Number {
				return Number(v1.localeCompare(v2));
			}
			function getStringVector(count:int):Vector.<String> {
				var vec:Vector.<String> = new Vector.<String>;
 
				for(var i:int = 0; i < count; i++) {
					vec.push(getRandomString());
				}
				//сортировка НЕ делается при поиске, она делается при генерации/изменении списка
				vec.sort(compare);
 
				return vec;
			}
 
			function getRandomString():String {
				var letters:Array = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];
 
				var letterCount:int = int(Math.random()*4 + 5);
 
				var str:String = '';
				while(--letterCount > 0) {
					str += letters[int(Math.random()*6)];
				}
 
				return str;
			}