Introduction to algorithms 3rd Edition

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)