Determining the optimal threshold value for a one-dimensional decision stump classifier I'm currently trying to find an efficient algorithm to solve a discrete optimization problem that arises when constructing decision trees. The problem is as follows:

Say we are given $N$ ordered data points on the real line: $x_1,\ldots,x_N \in \mathbb{R}$ such that $x_1 &lt; x_2 &lt; \ldots &lt; x_N$. 

Each of the points $x_i$ has a label $y_i \in \{0,1\}$. We are asked to predict this label using a decision stump classifier, $h(x;t) = \mathbb{1}[x&gt;t]$. The decision stump classifier predicts $\hat{y}_i = 1$ if $x_i &gt; t$. Thus, the accuracy of this classifier depends on the threshold parameter $t$. 

I am looking for an efficient algorithm to determine the value of $t$ that maximizes the number of correctly classified points. That is, solve the problem:

$$\max_{t\in\mathbb{R}} A(t)=\sum_{i=1}^N \mathbb{1}[y_i=0]\mathbb{1}[x_i\leq t] + \mathbb{1}[y_i=1]\mathbb{1}[x_i&gt;t]$$
Some insights:


Since there are $N$ data points, we only need to consider $N+1$ values of $t$. These are values that lie in the $N+1$ intervals $(-\infty,x_1), [x_1,x_2),\ldots, [x_{N-1},x_N), [x_N,\infty]$.
When $t &lt; \min_{i}x_i$, the decision stump predicts $\hat{y}_i=1$ for all $i=1,\ldots,N$. Here $A(t) = \sum_{i=1}^N{\mathbb{1}[y_i=1]}=N^+$.
When $t \geq \max_{i}x_i$, the decision stump predicts $\hat{y}_i=0$ for all $i=1,\ldots,N$. Here $A(t) = \sum_{i=1}^N{\mathbb{1}[y_i=0]}=N^-$.
The number of correctly classified points $A(t)$ can be decomposed as $B(t)+C(t)$, where
$$B(t) = \sum_{i=1}^N{\mathbb{1}[y_i=0]\mathbb{1}[x_i\leq t]}$$
is the number of correctly classified points with negative labels and
$$C(t) = \sum_{i=1}^N{\mathbb{1}[y_i=1]\mathbb{1}[x_i&gt;t]}$$
and the number of correctly classified points with positive labels. Note that $B(t)$ is monotonically increasing in $t$ while $C(t)$ is monotonically decreasing in $t$.
There is a straightforward algorithm that runs in $O(N)$ time, by scanning from left-to-right and right-to-left.  Basically, it takes advantage of a simple recurrence relation for $B(\cdot)$ and $C(\cdot)$.

Let $t_0,t_1,\dots,t_N$ denote a sequence of $N+1$ candidates for the threshold (i.e., $t_i \in [x_i,x_{i+1})$, etc.), as you articulated in the question.  Our job is to find the value of $i$ that maximizes $B(t_i)+C(t_i)$.

I claim we can compute the $N+1$ values $B(t_0),B(t_1),\dots,B(t_N)$ in $O(N)$ time, using a left-to-right scan.  This is because, given $B(t_{i-1})$, it is easy to compute $B(t_i)$.  In particular, notice that $B(t_i)$ can be written as the summation

$$B(t_i) = \sum_{j=1}^i 1[y_j=0].$$

In other words $B(t_i)$ is the count of how many of the first $y$'s are equal to zero.  Thus we get the recurrence relation

$$B(t_i) = B(t_{i-1}) + 1[y_i=0]$$

with the base case $B(t_0)=0$.  This allows us to compute all of the $B(t_i)$'s in $O(N)$ time.

We can similarly compute the $N+1$ values $C(t_0),C(t_1),\dots,C(t_N)$ in $O(N)$ time, by scanning from right-to-left.  Here we take advantage of a recurrence relation that computes $C(t_i)$ given $C(t_{i+1})$.  The details are similar to that for $B(\cdot)$.

The result is that we can compute the sequence of $N+1$ values $B(t_0)+C(t_0),B(t_1)+C(t_1),\dots,B(t_N)+C(t_N)$ in $O(N)$ time.  Then it is easy to find the largest value in that list.  The running time in total is $O(N)$ time.

I don't think you can do any better than $\Theta(N)$ worst-case running time, since you may need to examine every item (in the worst case).  Therefore,the method I have outlined above appears to be asymptotically optimal (up to constant factors).