Index: lib/sanitizer_common/sanitizer_common.h
===================================================================
--- lib/sanitizer_common/sanitizer_common.h
+++ lib/sanitizer_common/sanitizer_common.h
@@ -635,20 +635,19 @@
   }
 }
 
+// Works like std::lower_bound: finds the first element that is not less
+// than the val.
 template<class Container, class Value, class Compare>
 uptr InternalBinarySearch(const Container &v, uptr first, uptr last,
                           const Value &val, Compare comp) {
-  uptr not_found = last + 1;
-  while (last >= first) {
+  while (last > first) {
     uptr mid = (first + last) / 2;
     if (comp(v[mid], val))
       first = mid + 1;
-    else if (comp(val, v[mid]))
-      last = mid - 1;
     else
-      return mid;
+      last = mid;
   }
-  return not_found;
+  return first;
 }
 
 // Represents a binary loaded into virtual memory (e.g. this can be an
Index: lib/sanitizer_common/sanitizer_stackdepot.cc
===================================================================
--- lib/sanitizer_common/sanitizer_stackdepot.cc
+++ lib/sanitizer_common/sanitizer_stackdepot.cc
@@ -155,7 +155,7 @@
   IdDescPair pair = {id, nullptr};
   uptr idx = InternalBinarySearch(map_, 0, map_.size(), pair,
                                   IdDescPair::IdComparator);
-  if (idx > map_.size())
+  if (idx > map_.size() || map_[idx].id != id)
     return StackTrace();
   return map_[idx].desc->load();
 }
Index: lib/sanitizer_common/tests/sanitizer_common_test.cc
===================================================================
--- lib/sanitizer_common/tests/sanitizer_common_test.cc
+++ lib/sanitizer_common/tests/sanitizer_common_test.cc
@@ -172,13 +172,26 @@
 
 TEST(SanitizerCommon, InternalBinarySearch) {
   static const uptr kSize = 5;
-  uptr arr[kSize];
-  for (uptr i = 0; i < kSize; i++) arr[i] = i * i;
+  int arr[kSize];
+  arr[0] = 1;
+  arr[1] = 3;
+  arr[2] = 5;
+  arr[3] = 7;
+  arr[4] = 11;
 
-  for (uptr i = 0; i < kSize; i++)
-    ASSERT_EQ(InternalBinarySearch(arr, 0, kSize, i * i, UptrLess), i);
-
-  ASSERT_EQ(InternalBinarySearch(arr, 0, kSize, 7, UptrLess), kSize + 1);
+  EXPECT_EQ(0u, InternalBinarySearch(arr, 0, kSize, 0, UptrLess));
+  EXPECT_EQ(0u, InternalBinarySearch(arr, 0, kSize, 1, UptrLess));
+  EXPECT_EQ(1u, InternalBinarySearch(arr, 0, kSize, 2, UptrLess));
+  EXPECT_EQ(1u, InternalBinarySearch(arr, 0, kSize, 3, UptrLess));
+  EXPECT_EQ(2u, InternalBinarySearch(arr, 0, kSize, 4, UptrLess));
+  EXPECT_EQ(2u, InternalBinarySearch(arr, 0, kSize, 5, UptrLess));
+  EXPECT_EQ(3u, InternalBinarySearch(arr, 0, kSize, 6, UptrLess));
+  EXPECT_EQ(3u, InternalBinarySearch(arr, 0, kSize, 7, UptrLess));
+  EXPECT_EQ(4u, InternalBinarySearch(arr, 0, kSize, 8, UptrLess));
+  EXPECT_EQ(4u, InternalBinarySearch(arr, 0, kSize, 9, UptrLess));
+  EXPECT_EQ(4u, InternalBinarySearch(arr, 0, kSize, 10, UptrLess));
+  EXPECT_EQ(4u, InternalBinarySearch(arr, 0, kSize, 11, UptrLess));
+  EXPECT_EQ(5u, InternalBinarySearch(arr, 0, kSize, 12, UptrLess));
 }
 
 #if SANITIZER_LINUX && !SANITIZER_ANDROID