The array mentioned in the question are as follows:

[1,1,...,1,1,-1,-1,...,-1,-1]

How to quickly find the index of the 1 closest to -1?

Note: Both 1 and -1 will exist at the same time, and the number of 1 and -1 is large.

For example, for an array like this:

[1,1,1,1,1,-1,-1,-1]

the result should be 4.

The fastest way I can think of is binary search, is there a faster way?

CodePudding user response：

With the current representation of the data, binary search is the fastest way I can thing of. Of course, you can cache and reuse the results in constant time since the answer is always the same.

On the other hand if you change the representation of the array to some simple numbers you can find the next element in constant time. Since the data can always be mapped to a binary value, you can reduce the whole array to 2 numbers. The length of the first partition and the length of the second partition. Or the length of the whole array and the partitioning point. This way you can easily change the length of both partitions in constant time and have access to the next element of the second partition in constant time.

Of course, changing the representation of the array itself is a logarithmic process since you need to find the partitioning point.

CodePudding user response：

By a simple information theoretic argument, you can't be faster than log(n) using only comparisons. Because there are n possible outcomes, and you need to collect at least log(n) bits of information to number them.

If you have extra information about the statistical distribution of the values, then maybe you can exploit it. But this is to be discussed on a case-by-case basis.