diff --git a/crypto/stack/stack.c b/crypto/stack/stack.c
index ec557c0..599bd7b 100644
--- a/crypto/stack/stack.c
+++ b/crypto/stack/stack.c
@@ -56,6 +56,7 @@
 
 #include <openssl/stack.h>
 
+#include <assert.h>
 #include <string.h>
 
 #include <openssl/mem.h>
@@ -272,36 +273,39 @@
     return 0;
   }
 
-  // sk->comp is a function that takes pointers to pointers to elements, but
-  // qsort and bsearch take a comparison function that just takes pointers to
-  // elements. However, since we're passing an array of pointers to
-  // qsort/bsearch, we can just cast the comparison function and everything
-  // works.
+  // The stack is sorted, so binary search to find the element.
   //
-  // TODO(davidben): This is undefined behavior, but the call is in libc so,
-  // e.g., CFI does not notice. Unfortunately, |bsearch| is missing a void*
-  // parameter in its callback and |bsearch_s| is a mess of incompatibility.
-  const void *const *r = bsearch(&p, sk->data, sk->num, sizeof(void *),
-                                 (int (*)(const void *, const void *))sk->comp);
-  if (r == NULL) {
-    return 0;
-  }
-  size_t idx = ((void **)r) - sk->data;
-  // This function always returns the first result. Note this logic is, in the
-  // worst case, O(N) rather than O(log(N)). If this ever becomes a problem,
-  // restore https://boringssl-review.googlesource.com/c/boringssl/+/32115/
-  // which integrates the preference into the binary search.
-  while (idx > 0) {
-    const void *elem = sk->data[idx - 1];
-    if (call_cmp_func(sk->comp, &p, &elem) != 0) {
-      break;
+  // |lo| and |hi| maintain a half-open interval of where the answer may be. All
+  // indices such that |lo <= idx < hi| are candidates.
+  size_t lo = 0, hi = sk->num;
+  while (lo < hi) {
+    // Bias |mid| towards |lo|. See the |r == 0| case below.
+    size_t mid = lo + (hi - lo - 1) / 2;
+    assert(lo <= mid && mid < hi);
+    const void *elem = sk->data[mid];
+    int r = call_cmp_func(sk->comp, &p, &elem);
+    if (r > 0) {
+      lo = mid + 1;  // |mid| is too low.
+    } else if (r < 0) {
+      hi = mid;  // |mid| is too high.
+    } else {
+      // |mid| matches. However, this function returns the earliest match, so we
+      // can only return if the range has size one.
+      if (hi - lo == 1) {
+        if (out_index != NULL) {
+          *out_index = mid;
+        }
+        return 1;
+      }
+      // The sample is biased towards |lo|. |mid| can only be |hi - 1| if
+      // |hi - lo| was one, so this makes forward progress.
+      assert(mid + 1 < hi);
+      hi = mid + 1;
     }
-    idx--;
   }
-  if (out_index) {
-    *out_index = idx;
-  }
-  return 1;
+
+  assert(lo == hi);
+  return 0;  // Not found.
 }
 
 void *sk_shift(_STACK *sk) {
@@ -362,7 +366,10 @@
     return;
   }
 
-  // See the comment in sk_find about this cast.
+  // sk->comp is a function that takes pointers to pointers to elements, but
+  // qsort take a comparison function that just takes pointers to elements.
+  // However, since we're passing an array of pointers to qsort, we can just
+  // cast the comparison function and everything works.
   //
   // TODO(davidben): This is undefined behavior, but the call is in libc so,
   // e.g., CFI does not notice. Unfortunately, |qsort| is missing a void*