# How to find splitting point in [0,1] to maximize sum of sign function?

Given two $n$-number arrays $a_1, a_2, \ldots,a_n \in [0,1]$ and $b_1, b_2, \ldots,b_n \in [0,1]$. We would like to find the real number $x^{*} \in (0,1)$ s.t:

$x^{*} =\arg\max_{x} \sum_{i=1}^n \mathrm{sgn} \big( (a_i-x) (b_i -x)\big)$

Where $\mathrm{sgn} = 1$ if $x \geq 0$ and $\mathrm{sgn} = -1$ if $x < 0$

This question raised from my research work. I am looking for an efficient way to determine value of $x$.

WLOG, let $a_i < b_i$. Then $(a_1 - x)(b_i - x) \geq 0$ when $x \leq a_i \vee x \geq b_i$.
Keep a list of intervals $I$. For each $a_i , b_i$ add $(0, a_i]$ and $[b_i, 1)$ to the intervals. Now you just find point $x$ such that it lies within the most intervals in $I$.
• In other words, you sort $a_1,b_1,\ldots,a_n,b_n$, and then scan the result from left to right, keeping track of the number of intervals covering at each "event" point. Jul 2 '18 at 11:16