current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 6 down vote favorite
3

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.

condition1

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

condition2

and

condition3

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

share|improve this question
    
One solution is here: csee.umbc.edu/~kalpakis/courses/441-sp03/hws/hw4-sol.pdf –  Pepa Zapletal Mar 20 '14 at 9:47
    
This question appears to be off-topic because it is about computer science, and should be migrated to cs.stackexchange.com –  Blazemonger Mar 24 '14 at 21:43

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Algorithm Median of medians looks good. How can I use it? Do you have idea? –  Pepa Zapletal Mar 15 '14 at 11:34
    
No but you can try it yourself, and if you have a specific question, ask it on Stack Overflow –  Niklas B. Mar 15 '14 at 14:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.