<p>Alice and Bob have a different total number of candies. You are given two integer arrays <code>aliceSizes</code> and <code>bobSizes</code> where <code>aliceSizes[i]</code> is the number of candies of the <code>i<sup>th</sup></code> box of candy that Alice has and <code>bobSizes[j]</code> is the number of candies of the <code>j<sup>th</sup></code> box of candy that Bob has.</p>

<p>Since they are friends, they would like to exchange one candy box each so that after the exchange, they both have the same total amount of candy. The total amount of candy a person has is the sum of the number of candies in each box they have.</p>

<p>Return a<em>n integer array </em><code>answer</code><em> where </em><code>answer[0]</code><em> is the number of candies in the box that Alice must exchange, and </em><code>answer[1]</code><em> is the number of candies in the box that Bob must exchange</em>. If there are multiple answers, you may <strong>return any</strong> one of them. It is guaranteed that at least one answer exists.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> aliceSizes = [1,1], bobSizes = [2,2]
<strong>Output:</strong> [1,2]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> aliceSizes = [1,2], bobSizes = [2,3]
<strong>Output:</strong> [1,2]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> aliceSizes = [2], bobSizes = [1,3]
<strong>Output:</strong> [2,3]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= aliceSizes.length, bobSizes.length &lt;= 10<sup>4</sup></code></li>
	<li><code>1 &lt;= aliceSizes[i], bobSizes[j] &lt;= 10<sup>5</sup></code></li>
	<li>Alice and Bob have a different total number of candies.</li>
	<li>There will be at least one valid answer for the given input.</li>
</ul>

class Solution {
public:
bool found = false;// Mark if the target is found

/*
    Return:
    * Index of the found target
    * the index when binary search recursive function search_number()
      ends when target is inside [lower bound, upper bound]
*/
int search_number(int target, vector<int>& array, int start_index, int end_index) {
    int middle = 0;
    if (start_index == end_index) {
        if (target == array[start_index]) found = true;
        else found = false;

        return start_index;
    }
    middle = (start_index + end_index)/2;// Middle index
    if (target == array[middle]) {
        found = true;
        return middle;
    }
    else if (target > array[middle]){
        return search_number(target, array, middle+1, end_index);
    } else {
        return search_number(target, array, start_index, middle);
    }
    
    return 0;
}

    vector<int> fairCandySwap(vector<int>& aliceSizes, vector<int>& bobSizes) {
        vector<int> ret_vec(2);
        sort(aliceSizes.begin(), aliceSizes.end());
        sort(bobSizes.begin(), bobSizes.end());

        int sumA = 0, sumB = 0;
        for (int i = 0; i < aliceSizes.size(); i++) sumA += aliceSizes[i];

        for (int i = 0; i < bobSizes.size(); i++) sumB += bobSizes[i];

        int bob, alice;

        for (int i = 0; i < aliceSizes.size(); i++){
            alice = aliceSizes[i];
            bob = alice + (sumB - sumA)/2;
            search_number(bob, bobSizes, 0, bobSizes.size() - 1);
            if (found) {
                ret_vec[0] = alice;
                ret_vec[1] = bob;    
                return ret_vec;
            }
        }

        return ret_vec;
    }
};
43000