I did the same mistake in a second contest (at least), so I have to write this down...
When I have sorted array, I'm using binary search to find number of elements lower than some boundary value d. Problem is, that in Java, call Arrays.binarySearch(array, d) returns so called insertion point and it is valid to return for array let say 10, 20, 20, 20, 30 value 2 (0-based index, tried with Java 7) as the insertion point for searched value 20, but it doesn't mean that there are 2 elements lower than 20 in array... Solution that I used to finally fix my bug in both contests was to force the value d not to be in array, which I achieved by multiplying input by 2 (in problem C, contest 281 there are weak test cases), so there are no odd numbers in input...
In a future I'll rather implement my own binary search — it is easy and I do not need to handle negative return values...
Old code with Java binary search (works only with trick mentioned above):
int idx = Arrays.binarySearch(a, d);
if (idx < 0) {
idx = -idx - 1 - 1;
}
long lower = idx + 1;
My implementation of binary search for lower values in sorted array:
static long numberOfLowers(long d, long[] a) {
if ( a[0] >= d ) return 0;
if ( a[a.length - 1] < d ) return a.length;
int ok = 1; // at least a[0] is lower
int nok = a.length; // there are not so many items left
while ( ok + 1 < nok ) {
int mid = (ok + nok) >> 1;
if ( a[mid-1] < d ) {
ok = mid;
} else {
nok = mid;
}
}
return ok;
}
My solution with Java binary search — here.
The same, but with modified binary search — here.
I'd like to know from downvoters, what's wrong in my post...
Shouldn't it be idx = -idx — 1? For finding the number of lowers you could also create an array which saves the first occurrence of each element of a sorted array. Then do the binary search to find the position of the key and retrieve its first position from the pre computed array: Solution. Of course your solution has better space complexity but I think pre computing the first positions of each element is simpler.
Thanks for the tip, space complexity is typically not a big problem ;-)
What am I doing always, when using Java binary search is this calculation:
but from the information, that searched d is not in array, the element at position idx is greater, so to work with both (negative and positive index) I substracted 1 and added 1 out of
if, thanks for mentioning it (shown above).But it's the same either way (I guess that we are assuming that idx is the first occurrence of the key).
If you filled your array starting from 0 then
lower = idxeven if the key is not found (of course in that case you still have to turn idx into a positive number).In your first code lower would be correct if the key was not in the array because you would have
lower = -idx - 1 - 1 + 1 = -idx - 1.But if the key was found you would have
lower = idx + 1which would be right only if you were working with 1 based arrays.I wasted precious time yesterday because of figuring out whether to add or subtract something from idx even though its pretty trivial.
It shouldn't be necessary to handle the edge cases separately if written correctly, but it is easier to make off by one mistakes.
I prefer writing it this way:
It seems there is a bug in this code.
It should be
r = n - 1because it doesn't work for the case:d = 5; a = {10, 20}; n = 2It returns 2. Is it Ok?
Works fine for me https://ideone.com/DnQ2Sm.
How do you dig out 7 month old post?
Searched by tag 'java' :-)