[prev] 20 [next]

Analysis of Randomised Algorithms (cont)

If we cannot guarantee that the array contains any elements with key k

findKey(L,k,d):
|  Input  array L, key k, maximum #attempts d
|  Output some element in L with key k
|
|  repeat
|  |  if d=0 then
|  |     return failure
|  |  end if
|  |  randomly select e∈L
|  |  d=d-1
|  until key(e)=k
|  return e