Merge pull request #1404 from konstantinosalatzas/main

mhayter · web-flow · commit c61ffc16d032 · 2024-12-29T19:01:09.000-05:00
Fix typos in binary_search.md, bit-manipulation.md
diff --git a/src/algebra/bit-manipulation.md b/src/algebra/bit-manipulation.md
@@ -207,7 +207,7 @@ We can see that the all the columns except the leftmost have $4$ (i.e. $2^2$) se
 With the new knowledge in hand we can come up with the following algorithm:
 
 - Find the highest power of $2$ that is lesser than or equal to the given number. Let this number be $x$.
-- Calculate the number of set bits from $1$ to $2^x - 1$ by using the formua $x \cdot 2^{x-1}$.
+- Calculate the number of set bits from $1$ to $2^x - 1$ by using the formula $x \cdot 2^{x-1}$.
 - Count the no. of set bits in the most significant bit from $2^x$ to $n$ and add it.
 - Subtract $2^x$ from $n$ and repeat the above steps using the new $n$.
 
diff --git a/src/num_methods/binary_search.md b/src/num_methods/binary_search.md
@@ -82,10 +82,10 @@ f(0) \leq f(1) \leq \dots \leq f(n-1).
 $$
 
 The binary search, the way it is described above, finds the partition of the array by the predicate $f(M)$, holding the boolean value of $k < A_M$ expression.
-It is possible to use arbitrary monotonous predicate instead of $k < A_M$. It is particularly useful when the computation of $f(k)$ is requires too much time to actually compute it for every possible value.
+It is possible to use arbitrary monotonous predicate instead of $k < A_M$. It is particularly useful when the computation of $f(k)$ requires too much time to actually compute it for every possible value.
 In other words, binary search finds the unique index $L$ such that $f(L) = 0$ and $f(R)=f(L+1)=1$ if such a _transition point_ exists, or gives us $L = n-1$ if $f(0) = \dots = f(n-1) = 0$ or $L = -1$ if $f(0) = \dots = f(n-1) = 1$.
 
-Proof of correctness supposing a transition point exists, that is $f(0)=0$ and $f(n-1)=1$: The implementation maintaints the _loop invariant_ $f(l)=0, f(r)=1$. When $r - l > 1$, the choice of $m$ means $r-l$ will always decrease. The loop terminates when $r - l = 1$, giving us our desired transition point.
+Proof of correctness supposing a transition point exists, that is $f(0)=0$ and $f(n-1)=1$: The implementation maintains the _loop invariant_ $f(l)=0, f(r)=1$. When $r - l > 1$, the choice of $m$ means $r-l$ will always decrease. The loop terminates when $r - l = 1$, giving us our desired transition point.
 
 ```cpp
 ... // f(i) is a boolean function such that f(0) <= ... <= f(n-1)
