Betlista's blog

Few notes for a binary search
By Betlista, 9 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'd like to know from downvoters, what's wrong in my post...

→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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:

    idx = (-(insertion_point) - 1) // from JavaDoc
idx + 1 = -insertion_point
insertion_point = -idx -1

    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).

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 = idx even 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 + 1 which 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.

      → Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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:

int lower_bound(int d, int[] a, int n)
{
    int l=0, r=n;
    while (l < r)
    {
       int m = (l+r)/2;  //Important to floor the middle, otherwise it will not work when l+1=r
       if (a[m] < d)
          l = m + 1;
       else
          r = m;
    }
    return l;
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It seems there is a bug in this code.

    It should be r = n - 1 because it doesn't work for the case:

    d = 5; a = {10, 20}; n = 2

    It returns 2. Is it Ok?

    → Reply