2.3-6
INSERTION-SORT-2(A)
for j = 2 to A.length
key = A[j]
i = j-1
r = BINARY-SEARCH-R'(A, A[j], 1, i)
while i>r
A[i+1] = A[i]
i = i-1
A[i+1] = key
/* returns p in [1..A.length] / A[p] = v1 and v1 <= v if v1 exists
* returns 0 if v1 doesn't exist
*/
BINARY-SEARCH-R'(A, v, p, q)
if p>q
return 0
if A[ (p+q)/2 ] <= v
return max( (p+q)/2, BINARY-SEARCH-R'(A, v, (p+q)/2+1, q) )
else // A[ (p+q)/2 ] > v
return BINARY-SEARCH-R'( A, v, p, (p+q)/2-1 )
/* Iterative version
*/
BINARY-SEARCH-R'(A, v, p, q)
max_v : Integer
BEGIN
while p<=q
if A[ (p+q)/2 ] <= v
max_v = (p+q)/2
p = (p+q)/2+1
else // A[(p+q)/2] > v
q = (p+q)/2-1
if <=q
return max_v
else
return 0
END
2.3-7
Describe a O(n lg n)-time algorithm that, given a set S of n integers, and another integer x, determines whether or not exist 2 elements in S whose sum is exactly x
Hipótesis: Set S implementado como sorted array [1..length], BINARY-SEARCH definido como 0 cuando no existe el elemento buscado.
FIND-SUM-X-PAIR(S, x)
for j=1 to S.length-1
p = BINARY-SEARCH(S, x-S[j], j+1, S.length)
if p<>0
return (j,p)
Comentarios