Index: lldb/include/lldb/Utility/RangeMap.h
===================================================================
--- lldb/include/lldb/Utility/RangeMap.h
+++ lldb/include/lldb/Utility/RangeMap.h
@@ -712,6 +712,10 @@
     return lhs.GetRangeBase() < rhs.GetRangeBase();
   }
 
+  static bool BaseLessEqual(const Entry &lhs, const Entry &rhs) {
+    return lhs.GetRangeBase() <= rhs.GetRangeBase();
+  }
+
   uint32_t FindEntryIndexThatContains(B addr) const {
     const Entry *entry = FindEntryThatContains(addr);
     if (entry)
@@ -724,12 +728,18 @@
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
     assert(IsSorted());
 #endif
-
-    if (!m_entries.empty()) {
-      for (const auto &entry : m_entries) {
-        if (entry.Contains(addr))
-          indexes.push_back(entry.data);
-      }
+    if (m_entries.empty())
+      return indexes.size();
+
+    // Find the first range which base address is higher than the address
+    // we are looking for. This address can't contain the address we are
+    // looking for. All addresses after also can't contain our address as
+    // we sorted our ranges by base address.
+    auto end = std::lower_bound(m_entries.begin(), m_entries.end(),
+                                Entry(addr, 1), BaseLessEqual);
+    for (auto I = m_entries.begin(); I != end; ++I) {
+      if (I->Contains(addr))
+        indexes.push_back(I->data);
     }
     return indexes.size();
   }