Найти средний элемент в граф отсортированного массива

Question

Итак, у меня есть массив как это:

a[1] = 2 
a[4] = 3 
a[8] = 1 

, которые представляют эту последовательность 1 1 4 4 4 8

И мне нужно найти средний элемент или элемент, прежде чем (для четных и нечетных); В этом примере его 4.

Как это сделать быстро?

Мой код очень медленно:

static int B(int[] array, int size) {  
    int c = 0; 
    for (int i = 0; i < array.length; i++) { 
     for (int j = 0; j < array[i]; j++) { 
      c++; 
      if (c == size/2) { 
       return i;  
      } 
     } 
    } 
} 

Answer 1

1. Traverse исходного массива и добавить все значения

   a[1] = 2 
   a[4] = 3 
   a[8] = 1 
   sum = 6 
   

2. Разделить сумму на 2 (найти середине)

   mid = 6/2 = 3 
   

3. Траверс оригинал a rray и вычитать значение из суммы

   check if ans <= 0 
   if true print index 
   else continue to next 
   

Answer 2

Для еще менее эффективный способ сделать это, запустить один проход через и постоянно обновлять :)

Javascript (так как я Java вызов):

var a=[] 

a[1] = 2 
a[4] = 3 
a[8] = 1 
a[9] = 2 
a[10] = 3 
a[11] = 1 
//1 1 4 4 4 8 9 9 10 10 10 11 

function middle (arr){ 
    var stack = [], 
     total = 0, 
     tmp, 
     tmpChange, 
     middle = 0, 
     change = 0, 
     middleElement 

    for (i in arr){ 
    stack.push([i, arr[i]]) 
    total += arr[i] 
    tmp = Math.ceil(total/2) 
    change = tmp - middle 
    middle = tmp 

    while (change){ 
     tmpChange = stack[0][1] - change 

     if (tmpChange >= 0) { 
     stack[0][1] = tmpChange 
     change = 0 
     } 
     else { 
     change -= stack[0][1] 
     stack.splice(0,1) 
     } 
    } 

    middleElement = stack[0][0] 
    } 

    return middleElement 
} 

console.log(middle(a))