Design of algorithms by division and conquest

The algorithm would look something like this:

função z(int[n] A, int[n] B, int x) {     // Linha 1
    C = copy(B)                           // Linha 2
    sort(C)                               // Linha 3
    int i, k = -1                         // Linha 4
    for (i = 0; i < n && k == -1; i++) {  // Linha 5
        k = binary_search(C, x - A[i])    // Linha 6
    }                                     // Linha 7
    if (k == -1) return [-1, -1]          // Linha 8
    j = indexof(B, C[k])                  // Linha 9
    return [i, j]                         // Linha 10
}                                         // Linha 11

In this algorithm:

• copy is the function that creates a copy of an array.
• sort is the function that sorts an array.
• binary_search is the function that searches for an element in an ordered array using the binary search and returns the position where the element is found. -1 is returned if the element is not found.
• indexof is the function that returns at which position of an array (possibly cluttered) a particular element is found.

The function returns a pair of elements that correspond to the [i, j] positions of the searched elements. If there is no i and j such that A[i] + B[j] = x , then [-1, -1] is returned.

The idea is for you to create an ordered copy of B called C. With this you can cycle through each position of A using i as counter and searching by means of binary search the corresponding element in C in a position k . If the C search is never successful after the entire array A has been traversed, then [-1, -1] is returned. Otherwise, when the binary search succeeds, the correct value of i is determined and then just look at B the element in C[k] to find the value of j .

The complexity of line 2 is O (n) .

• The complexity of line 3 is O (n log n) . To do so, simply use an algorithm such as mergesort as the sort implementation.

• Each iteration of line 6 has a complexity of O (log n) .

• Thus, the total complexity of the loop of lines 5-7 is O (n log n) .

• Line 9 has complexity O (n) in the worst case. A sequential search on B is sufficient.

• Lines 4, 8 and 10 have complexity O (1) .

There is one however only. This is not a division-and-conquest algorithm. However, this may serve you at least as a basis for producing one.