Update binary_search.md

adamant-pwn · adamant-pwn · commit 2d5a8ea65086 · 2023-11-30T00:02:44.000+01:00
diff --git a/src/num_methods/binary_search.md b/src/num_methods/binary_search.md
@@ -60,7 +60,7 @@ Then the implementation could look like this:
 ... // a sorted array is stored as a[0], a[1], ..., a[n-1]
 int l = -1, r = n;
 while (r - l > 1) {
-    int m = l + (r - l) / 2;
+    int m = (l + r) / 2;
     if (k < a[m]) {
         r = m; // a[l] <= k < a[m] <= a[r]
     } else {
@@ -71,7 +71,7 @@ while (r - l > 1) {
 
 During the execution of the algorithm, we never evaluate neither $A_L$ nor $A_R$, as $L < M < R$. In the end, $L$ will be the index of the last element that is not greater than $k$ (or $-1$ if there is no such element) and $R$ will be the index of the first element larger than $k$ (or $n$ if there is no such element).
 
-**Note.** If one calculates `m` as follows `m = (r + l) / 2` it can lead to overflow. It is funny fact that this error lived about 9 years in JDK as described in the [blogpost](https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html).
+**Note.** Calculating `m` as `m = (r + l) / 2` can lead to overflow if `l` and `r` are two positive integers, and this error lived about 9 years in JDK as described in the [blogpost](https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html). Some alternative approaches include e.g. writing `m = l + (r - l) / 2` which always works for positive integer `l` and `r`, but might still overflow if `l` is a negative number. If you use C++20, it offers an alternative solution in the form of `m = std::midpoint(l, r)` which always works correctly.
 
 ## Search on arbitrary predicate
 
@@ -91,7 +91,7 @@ Proof of correctness supposing a transition point exists, that is $f(0)=0$ and $
 ... // f(i) is a boolean function such that f(0) <= ... <= f(n-1)
 int l = -1, r = n;
 while (r - l > 1) {
-    int m = l + (r - l) / 2;
+    int m = (l + r) / 2;
     if (f(m)) {
         r = m; // 0 = f(l) < f(m) = 1
     } else {
