1
$\begingroup$

Let $n$ be a positive integer and $f \colon \{1,\dots,n\} \to \mathbb{R}$ be a decreasing function with $f(1) \ge 1$. We are interested in finding the largest number $k\in \{1,\dots,n\}$ such that $f(k) \ge 1$.

It is not possible to analytically find the largest $k$ by solving the inequality $f(k) \ge 1$. I realized that we can use Binary Search Algorithm to find $k$. It is a good option because the number of operations required to find $k$ in the worst case is bounded by $\mathcal{O}(\log n)$. Here is how I write a binary search algorithm for this problem: \begin{align} &l \gets 1\\ &u \gets n\\ &\texttt{while }\ \ l \le u\\ & \ \ \ \ \ \ \ \ \ \ m \gets \left\lfloor \frac{l+u}{2} \right\rfloor\\ & \ \ \ \ \ \ \ \ \ \ \texttt{if }\ \ f(m) \ge 1\\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ l \gets m + 1\\ & \ \ \ \ \ \ \ \ \ \ \texttt{else }\\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ u \gets m - 1\\ & \ \ \ \ \ \ \ \ \ \ \texttt{end if }\\ &\texttt{end while }\\ &\texttt{return }\ u \end{align} The algorithm terminates by giving $u$ as the largest $k\in \{1,\dots,n\}$ satisfying $f(k) \ge 1$. Solving a few numerical examples, I think the algorithm works properly. However, I want to know how we can prove that for any given $n$ and $f(\cdot)$ it gives a correct result. Any suggestions? Basically, I'm looking for a rigorous proof that why the sequence of numbers assigned to $u$ converges to the largest $k\in \{1,\dots,n\}$ satisfying $f(k) \ge 1$.

$\endgroup$
1
$\begingroup$

As I mentioned in my comment to another answer the current algorithm has some non-intuitive behavior (upper limit is less than lower limit on loop exit). For the sake of reasoning, IMO eliminating non-intuitive behavior helps.

I suggest writing the algorithm recursively and then show that if an invocation with a particular set of inputs is correct, then an invocation with that set plus an additional element is correct. In other words use induction. Here is a useful post on the subject: https://stackoverflow.com/questions/9538562/general-proof-strategies-to-show-correctness-of-recursive-functions.

As an example:

\begin{align} \ &\text{// make sure at least one element is } \geq 1\\ \ &\text{assert } f(0) \geq 1\\ \ &bs(1, upper, middleOut)\\ \\ \ \text{fun}& \text{ction bs( lower, upper, middleOut)}\\ & \text{// middleOut is an output parameter}\\ & \text{assert } lower \leq upper\\ &\text{if } lower = upper\\ &\ \ \ \text{if } f(lower) \geq 1 \\ &\ \ \ \ \ \ \text{return }f(lower)\\ &\ \ \ \text{else}\\ &\ \ \ \ \ \ \text{return }f(lower-1)\\ &\ \ \ \text{end if}\\ &\text{end if}\\ \\ &middleOut \gets (lower+upper)/2\\ &\text{if }f(middleOut) \geq 1\\ &\ \ \ \text{return } bs(middleOut+1, upper, middleOut)\\ &\text{else}\\ &\ \ \ \text{return } bs(lower, middleOut, middleOut, result)\\ &\text{end if} \end{align}

The recursion termination part at the beginning is clearly correct. First it ensures the function stops. Either $lower$ increases or $upper$ decreases on each recursion, so eventually they equal each other (or else first assert is hit, which means there is a bug)

Functionally it's correct also. If we are searching an array slice of length one (ie $upper = lower$), the array slice either has it's one element $\geq 1$ or else it doesn't and the element proceeding slice is $\geq 1$ (this assertion is proved by examining recursive code and noting that $f(1) \geq 1$).

The recursive code is invoked if $lower < upper$. On each invocation $middleOut$ is set: $lower \leq middleOut < upper$ (the $\leq$ is because the divide by two rounds down). Thus $middleOut$ is always within expected range.

$lower$ is always set $\leq upper$, because when it increases, it increases to $middleOut+1$ and since $middleOut < upper$ then $middleOut+1 \leq upper$.

There are two cases to consider to show $upper$ is always set $\geq lower$. First case is if $lower < middleOut$ then $upper \gets middleOut$. This ensures $lower < upper$. Second case is if $lower = middleOut$. In this case $upper \gets middleOut$ and $lower = upper$

Case 1) If $f(middleOut) \geq 1$ then the desired element's index $\geq middleOut$. Invoking the binary search again as $bs(middleOut+1,upper,middleOut)$ either finds the desired element in the range $middleOut+1$ to $upper$ or else all elements in that range are $< 1$. When $bs(middleOut+1,upper,middleOut)$ finally terminates, it either returns the desired element from the range, or else the element immediately before the range.

Case 2) If $f(middleOut) < 1$ then the desired element's index $< middleOut$. Invoking the binary search again as $bs(lower, middleOut,middleOut)$ finds the desired element.

So in both cases if $bs$ works with a set of numbers, then $bs$ works with a superset of those numbers.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

This is a very basic computer science result wrapped up in lot of mathematical notation. Basically, you have $n$ elements in an array and each entry corresponds to the sample of the function at that index. Thus, if $i$ is the position, then $f(i)$ is the value. It is already given that $f(i)$ is a decreasing function. Thus $f(i)>f(i+1)$ for all $i$. Thus $f(1)$ is the largest. Basically, the array is already sorted for you. Now, if it wasn't, to find the largest element in an array is a linear operation, i.e. order of $O(n)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I'm looking for a rigorous proof that why the sequence of numbers assigned to $u$ converges to the largest $k\in \{1,\dots,n\}$ satisfying $f(k) \ge 1$. If $\ell$ is the optimal value, I want to see why the algorithm does not converge to $\ell-1$ or $\ell+1$. $\endgroup$ – Opt Oct 10 '17 at 4:33
1
$\begingroup$

Hint: let $k \in \{ 1, \ldots, n \}$ be the solution to the problem. Prove that the $\texttt{while}$ loop has the following invariant: $l-1 \leqslant k \leqslant u$ and that $u-l$ decreases, hence the algorithm stops.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ If $\ell$ is the optimal value, I want to see why the algorithm does not converge to $\ell-1$ or $\ell+1$. $\endgroup$ – Opt Oct 10 '17 at 4:34
  • 1
    $\begingroup$ @Opt actually $u$ ($k=u$ because algorithm returns $u$) will always be less than $l$ at termination, otherwise the loop won't exit. I'm fairly certain that $u$ will always be $l-1$ when the loop exits. In fact $u$ can be zero or $l$ can be $n+1$ when the loop exits. $\endgroup$ – Χpẘ Oct 10 '17 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.