Use the fact that some index lists are sorted.

pkg/analysis_server/lib/src/services/index2/index2.dart

 // Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 import 'dart:async';
 
 import 'package:analyzer/dart/ast/ast.dart';
 import 'package:analyzer/dart/element/element.dart';
 import 'package:analyzer/src/generated/source.dart';
 import 'package:analyzer/src/summary/format.dart';
@@ skipping 204 matching lines @@
 
 /**
  * Helper for requesting information from a single [PackageIndex].
  */
 class _PackageIndexRequester {
   final PackageIndex index;
 
   _PackageIndexRequester(this.index);
 
   /**
-   * Return the [element]'s identifier in the [index] or `null` if the
+   * Return the [element]'s identifier in the [index] or `-1` if the
    * [element] is not referenced in the [index].
    */
   int findElementId(Element element) {
     // Find the id of the element's unit.
     int unitId = getUnitId(element);
-    if (unitId == null) {
-      return null;
+    if (unitId == -1) {
+      return -1;
     }
     // Prepare the offset of the element.
     int offset = element.nameOffset;
     if (element is LibraryElement || element is CompilationUnitElement) {
       offset = 0;
     }
     // Find the first occurrence of an element with the same offset.
     int elementId = _findFirstOccurrence(index.elementOffsets, offset);
     if (elementId == -1) {
-      return null;
+      return -1;
     }
     // Try to find the element id using offset, unit and kind.
     IndexSyntheticElementKind kind =
         PackageIndexAssembler.getIndexElementKind(element);
     for (;
         elementId < index.elementOffsets.length &&
             index.elementOffsets[elementId] == offset;
         elementId++) {
       if (index.elementUnits[elementId] == unitId &&
           index.elementKinds[elementId] == kind) {
         return elementId;
       }
     }
-    return null;
+    return -1;
   }
 
   /**
    * Complete with a list of locations where elements of the given [kind] with
    * names satisfying the given [regExp] are defined.
    */
   List<Location> getDefinedNames(RegExp regExp, IndexNameKind kind) {
     List<Location> locations = <Location>[];
     for (UnitIndex unitIndex in index.units) {
       _UnitIndexRequester requester = new _UnitIndexRequester(this, unitIndex);
       List<Location> unitLocations = requester.getDefinedNames(regExp, kind);
       locations.addAll(unitLocations);
     }
     return locations;
   }
 
   /**
    * Complete with a list of locations where the given [element] has relation
    * of the given [kind].
    */
   List<Location> getRelations(Element element, IndexRelationKind kind) {
     int elementId = findElementId(element);
-    if (elementId == null) {
+    if (elementId == -1) {
       return const <Location>[];
     }
     List<Location> locations = <Location>[];
     for (UnitIndex unitIndex in index.units) {
       _UnitIndexRequester requester = new _UnitIndexRequester(this, unitIndex);
       List<Location> unitLocations = requester.getRelations(elementId, kind);
       locations.addAll(unitLocations);
     }
     return locations;
   }
 
   /**
    * Return the identifier of [str] in the [index] or `-1` if [str] is not used
    * in the [index].
    */
   int getStringId(String str) {
-    return index.strings.indexOf(str);
+    return binarySearch(index.strings, str);
   }
 
   /**
    * Return the identifier of the [CompilationUnitElement] containing the
    * [element] in the [index] or `-1` if not found.
    */
   int getUnitId(Element element) {
     CompilationUnitElement unitElement =
         PackageIndexAssembler.getUnitElement(element);
     int libraryUriId = getUriId(unitElement.library.source.uri);
+    if (libraryUriId == -1) {
+      return -1;
+    }
     int unitUriId = getUriId(unitElement.source.uri);
+    if (unitUriId == -1) {
+      return -1;
+    }
     for (int i = 0; i < index.unitLibraryUris.length; i++) {
       if (index.unitLibraryUris[i] == libraryUriId &&
           index.unitUnitUris[i] == unitUriId) {
         return i;
       }
     }
     return -1;
   }
 
   /**
@@ skipping 99 matching lines @@
       }
     }
     return locations;
   }
 
   /**
    * Complete with a list of locations where a class members with the given
    * [name] is referenced with a qualifier, but is not resolved.
    */
   List<Location> getUnresolvedMemberReferences(String name) {
+    // Find the name ID in the package index.
+    int nameId = packageRequester.getStringId(name);
+    if (nameId == -1) {
+      return const <Location>[];
+    }
+    // Find the first usage of the name.
+    int i =_findFirstOccurrence(unitIndex.usedNames, nameId);
+    if (i == -1) {
+      return const <Location>[];
+    }
+    // Create locations for every usage of the name.
     List<Location> locations = <Location>[];
     String unitLibraryUri = null;
     String unitUnitUri = null;
-    for (int i = 0; i < unitIndex.usedNames.length; i++) {
-      int nameIndex = unitIndex.usedNames[i];
-      if (packageRequester.index.strings[nameIndex] == name) {
-        unitLibraryUri ??= packageRequester.getUnitLibraryUri(unitIndex.unit);
-        unitUnitUri ??= packageRequester.getUnitUnitUri(unitIndex.unit);
-        locations.add(new Location(unitLibraryUri, unitUnitUri,
-            unitIndex.usedNameOffsets[i], name.length, true));
-      }
+    for (; i < unitIndex.usedNames.length &&
+        unitIndex.usedNames[i] == nameId; i++) {
+      unitLibraryUri ??= packageRequester.getUnitLibraryUri(unitIndex.unit);
+      unitUnitUri ??= packageRequester.getUnitUnitUri(unitIndex.unit);
+      locations.add(new Location(unitLibraryUri, unitUnitUri,
+          unitIndex.usedNameOffsets[i], name.length, true));
     }
     return locations;
   }
 }