You are given two arrays - both sorted and a distance d.
The numbers in array1 and array2 are both distinct ( no overlap )
eg -
Array1 - 0,2,4,9,11,13,14,16,18
Array2 - 5, 8, 19
d = 6
You have to return total count where element of Array1 and Array2 are within distance d.
Pick smaller array.
- taking element at index 0 of Array2.
stRange = 5-5 = 0;
enRange = 5+5 = 10;
now do binary seach to get number of elements withing range 0-10 --> 0,2,4,9
we get back 4
add to result.
Result = 4;
- taking element at index 1 of Array2.
stRange = 8-5 = 3;
enRange = 8+5 = 13;
now do binary seach to get number of elements withing range 3-13 --> 4,9,11,13
we get back 4
add to result.
Result = 4+4 = 8;
3)taking element at index 2 of Array2.
stRange = 19-5 = 14;
enRange = 19+5 = 24;
now do binary seach to get number of elements withing range 14-24 --> 14,16,18
we get back 2
add to result.
Result = 4+4+3 = 11;
Answer -- 11
I was able to talk the algo out, but the binary search to find range, I couldn't. Can someone tell me how you find the number of elements within the range. It should return 0, if that range is not to be found.