CODEWITHSUNDEEP
javaalgorithmsorting
JohnDow
JohnDow

Reputation: 1322

Find middle element in Count sorted array

So, I have array like this:

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

which represent this sequence 1 1 4 4 4 8

And I need to find middle element, or element before (for odd and even); In this example its 4.

How can I do this quick?

My code is very slow:

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;    
            }
        }
    }   
}

Upvotes: 0

Views: 5022

Answers (2)

גלעד ברקן
גלעד ברקן

Reputation: 23955

For an even less efficient way to do it, run one pass through and keep updating :)

Javascript (since I'm Java challenged):

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))

Upvotes: 0

noMAD
noMAD

Reputation: 7844

  1. Traverse original array and add all values

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

  2. Divide sum by 2 (find mid)

    mid = 6/2 = 3

  3. Traverse original array and subtract value from sum

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

Upvotes: 5

Related Questions