Determining the optimal threshold value for a one-dimensional decision stump classifier
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).