algorithm - Find Rank of element in unsorted array in complexity:O(lg n).Any other better approach than this? -

given numbers in unsorted way x:{4,2,5,1,8,2,7}

how find rank of number??

eg: rank of 4:4 : rank of 5:5

complexity has o(lg n).

it can done in complexity of o(lg n) of red black trees , augmented data structure approach(one of fascinating stuff nowadays). lets make use of order statistic treeorder statistic tree

algorithm: rank(t,x)  //t: order-statistic tree, x: node(to find rank of node) r = x.left.size + 1 y=x while y != t.root     if y==y.p.right         r= + y.p.left.size + 1     y=y.p return r; 

any appreciated.

are there better approach this??

given numbers in unsorted way, x:{4,2,5,1,8,2,7}

how find rank of number?

rank position of element when sorted.

complexity has o(lg n).

that's impossible. have @ each element @ least once. thus, can't better o(n), , it's trivial in o(n):

• set found false
• set smaller 0
• for each number in array
  • if number smaller needle
    • increment smaller counter
  • if number equal needle
    • set found true
• if found, return smaller+1, else return error

---

it can done in complexity of o(lg n) of red black trees , augmented data structure approach(one of fascinating stuff nowadays). let's make use of order statistic tree

the problem don't have order-statistic tree, , don't have time build one. building order-statistic tree takes more o(lg n) time*.

---

but let's have time build order-statistic tree. since extracting sorted list of nodes in binary search tree takes linear time, building order-statistic tree cannot faster sorting array directly.

so, let's sort array directly. then, finding rank of element equivalent finding element in sorted array. known task can solved in o(lg n) via binary search (repeatedly split array in half until find element). turns out order-statistic tree not, quite, help. in fact, can imagine binary search lookup in order-statistic tree (except tree doesn't exist).

---

if x change @ runtime, order-statistic trees help. then, element removal/addition takes th(lg n) (worst-case) time, while takes th(n)* (average-case) in ordinary sorted array because need shift elements around. x immutable, order-statistic trees don't speed on plain arrays.

---

* technically, o(lg n) set of functions grow asymptotically no more lg n. when "more o(lg n)", correct interpretation "more every function in o(lg n). incidentally, equivalent saying run time omega(lg n) (note omega lowercase).

th(lg n) set of functions asymptotically equal lg n, constant. expressing same using o(lg n) , english while staying technically correct awkward.