Algorithm - Search for an Optimal Array Element

Question

I have an array of mutually different elements (x_1, x_2, ..., x_n). Each element binds a positive value (w_1, w_2, ..., w_n). The sum of these positive values ​​is 1.

I need to find the Optimal Element (x_k) which:

and

I find this algorithm:

proc OptimalElement(arr[]) prevs_w := 0 nexts_w := 0 for (i = 0; i <= n; i++) { wi := arr[i].w nexts_w := 1 - prevs_w - wi IF (prevs_w < 0,5 && nexts_w <= 0,5) THEN return arr[i] ELSE prevs_w := prevs_w + wi ENDIF } end 

But this algorithm only compares the sum of the elements whose index is i <k and i> k. But I need an algorithm that calculates the sum of the elements that x_i <x_k and x_i> x_k.

The algorithm should work with O (n) time. Do you have an idea how to solve it? thanks for the tips.

Input Example:

x_i | 1; 4; 2; 3; 5
w_i | 0.1; 0.2; 0.3; 0.2; 0.2

Answer 1

You can use Quickselect :

• Choose a rod (randomly would be a good idea)
• Divide the array around this axis in accordance with their x coordinates, keeping track of the amount of objects that you put in its direction
• If s ≥ 1/2, write to the left. Otherwise, go back to the right.

The problem is that the execution time is O (n²) in the worst case. However, this is O (n) on average (provided that the elements are somewhat evenly distributed). There are other selection algorithms based on partitions with deterministic linear time that you can probably adapt in a similar way, but they are more complicated.