Algorithm - Find Optimal element of an array

Question

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

I have to find an Optimal element (x_k), which is:

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 compare only sum of items which index is i < k and i > k. But I need algorithm that calculate sums of items which x_i < x_k and x_i > x_k.

An Algorithm should have work with O(n) time. Do you have any idea how to solve it? Thx for tips.

Example of input:

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:

1. Select a pivot (randomly would be a good idea)
2. Partition the array around that pivot according to their x coordinates, keeping track of the sum s of items you put to the left side of it
3. If s ≥ 1/2, recurse into the left side. Else, recurse into the right side

The problem here is the run time is O(n²) in the worst case. However, it is O(n) on average (assuming the elements are somewhat evenly distributed). There are other partition-based selection algorithms with deterministic linear time which you can probably adapt in a similar way, but they are more complicated.