# How to use Binary Search with "4Sum II"?

• This question has "Binary Search" as a tag but in the solutions proposed (in discuss) I don't see it used. How is that?
Is it actually possible to use binary search to solve such problem?

• @SergeGardien Yes~first add x (foreach in vector A) and y (foreach in vector B) ,put the sum into vector s,do the same to vector C,D and new vector called m; for every x in new vector s, we find how many -x in vector m, use binary search to do this ,This is the binary search code:

``````    int biSearch(vector<int> & nums,int x,bool LEFT) {
int l = 0, r = nums.size()-1, m = 0;
while (l <= r) {
m = (l+r)>>1;
if (LEFT) {
if (nums[m] >= x) r = m - 1;
else l = m + 1;
}
else {
if (nums[m] <= x) l = m + 1;
else r = m - 1;
}
}
return LEFT?l:r;
}
``````

we only need to call `biSearch(m,-s[i],false)-biSearch(m,-s[i],true)+1` to calc the number of -s[i] in vector m;
This is my code, 216ms beats 89.09%

``````class Solution {
public:
int biSearch(vector<int> & nums,int x,bool LEFT) {
int l = 0, r = nums.size()-1, m = 0;
while (l <= r) {
m = (l+r)>>1;
if (LEFT) {
if (nums[m] >= x) r = m - 1;
else l = m + 1;
}
else {
if (nums[m] <= x) l = m + 1;
else r = m - 1;
}
}
return LEFT?l:r;
}
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
vector<int> s;
vector<int> m;
int sum = 0, ans = 0, n = A.size();
for (int i = 0; i < n; ++ i) {
for (int j = 0; j < n; ++ j) {
s.push_back(A[i]+B[j]);
m.push_back(C[i]+D[j]);
}
}
sort(s.begin(),s.end());
sort(m.begin(),m.end());
for (size_t i = 0; i < s.size(); ++ i) {
if (i != 0 && s[i] == s[i-1]) ans += sum;
else {
sum = biSearch(m,-s[i],false)-biSearch(m,-s[i],true)+1;
ans += sum;
}
}
return ans;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.