Zed - 1 year ago 88
Java Question

# Finding a case when binary search fails

I am trying to solve a really interesting programming challenge and I'm sort of out of the ideas why my code fails. Here it is:

Write a function that, given a list and a target sum, returns
zero-based indices of any two distinct elements whose sum is equal to
the target sum. If there are no such elements, the function should
return null.
For example, findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12) should return any of the following tuples of indices:

``````1, 4 (3 + 9 = 12)
2, 3 (5 + 7 = 12)
3, 2 (7 + 5 = 12)
4, 1 (9 + 3 = 12)
``````

Should be simple right? So here's my function:

``````public static int[] findTwoSum(int[] list, int sum) {
int[] indices = null;
for(int i = 0; i < list.length; i++) {
int currentNum = list[i];
int findNum = sum - currentNum;
int length = list.length;
int min = i;
int max = length-1;

while(max >= min) {
int guess = (max+min)/2;

if(list[guess] == findNum) {
return new int[] {i,guess};
}

if(list[guess] < findNum) {
min = guess + 1;
}

if(list[guess] > findNum) {
max = guess - 1;
}
}

}

return indices;
}
``````

Code is pretty simple, for every element in the array, it tries to find using binary search, another element, so that their sum is equal to the provided
`sum`
. I've tested this code and I couldn't find scenario where it fails, assuming that the provided array is sorted. However, when I run this code on TestDome , the last case fails, it is somehow wrong solution. Could anybody point out what is wrong with this approach ?

A faster approach is to put the data into a hash map with counts and original indexes, and check for presence of `Target - n` for each `n` in the list. You need counts for the special case when `Target` is equal to `2*n`.