[prev] 18 [next]

Analysis of Randomised Algorithms

Randomised algorithm to find some element with key k in an unordered array: 

findKey(L,k):
|  Input  array L, key k
|  Output some element in L with key k
|
|  repeat
|     randomly select e∈L
|  until key(e)=k
|  return e