diff --git a/lldb/include/lldb/Utility/RangeMap.h b/lldb/include/lldb/Utility/RangeMap.h
--- a/lldb/include/lldb/Utility/RangeMap.h
+++ b/lldb/include/lldb/Utility/RangeMap.h
@@ -540,14 +540,13 @@
     if (!m_entries.empty()) {
       typename Collection::const_iterator begin = m_entries.begin();
       typename Collection::const_iterator end = m_entries.end();
-      typename Collection::const_iterator pos =
-          std::lower_bound(begin, end, range, BaseLessThan);
-
-      while (pos != begin && pos[-1].Contains(range))
-        --pos;
+      typename Collection::const_iterator limit =
+          std::upper_bound(begin, end, range, BaseLessThan);
 
-      if (pos != end && pos->Contains(range))
-        return &(*pos);
+      for (auto pos = begin; pos < limit; ++pos) {
+        if (pos->Contains(range))
+          return &(*pos);
+      }
     }
     return nullptr;
   }
diff --git a/lldb/unittests/Utility/RangeMapTest.cpp b/lldb/unittests/Utility/RangeMapTest.cpp
--- a/lldb/unittests/Utility/RangeMapTest.cpp
+++ b/lldb/unittests/Utility/RangeMapTest.cpp
@@ -53,10 +53,7 @@
   // With overlapping intervals, the intention seems to be to return the first
   // interval which contains the address.
   EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0));
-
-  // However, this does not always succeed.
-  // TODO: This should probably return the range (0, 40) as well.
-  EXPECT_THAT(Map.FindEntryThatContains(35), nullptr);
+  EXPECT_THAT(Map.FindEntryThatContains(35), EntryIs(0));
 }
 
 TEST(RangeDataVector, CustomSort) {