Zed Zed - 15 days ago 5
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 ?

Answer

The code assumes that the list is sorted. The problem statement does not say anything about the order of elements, so you need to sort the array yourself. Since you need indexes, you need to sort pairs of values and indexes.

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.

Comments