V
failure
ariation: Linear Search with Ordered Array (early stop possible)
Here,
-
i
|
Instance
|
pi
|
Ti(n)
|
1
|
x = A[1]
|
p/n
|
1
|
2
|
x = A[2]
|
p/n
|
2
|
i
|
x = A[i]
|
p/n
|
i
success
|
n
|
x = A[n]
|
p/n
|
n
|
n+1
|
x < A[1]
|
(1 – p)/n
|
1
|
n+2
|
x < A[2]
|
(1 – p)/n
|
2
|
j
|
x < A[j]
|
(1 – p)/n
|
j
|
2n-1
|
x < A[2n-1]
|
(1 – p)/n
|
n-1
|
2n
|
x < A[n]
|
(1 – p)/n
|
n
|
For linear search with ordered array,
A(n) = 
=  = 
= 
= 
=  = 
Share with your friends: |
