15
\$\begingroup\$

What do you think about this simple implementation of B search in Java?

public static boolean find(int[] arrayToScan, int valueToFind) {
    int startIndex = 0, endIndex = arrayToScan.length, midleIndex;
    while (true) {
        midleIndex = (startIndex + endIndex) / 2;
        if (arrayToScan[midleIndex] == valueToFind) {
            return true;
        }
        if (startIndex >= endIndex || midleIndex == 0 || midleIndex == arrayToScan.length - 1) {
            return false;
        }
        if (valueToFind > arrayToScan[midleIndex]) {
            startIndex = midleIndex+1 ;
        }
        if (valueToFind < arrayToScan[midleIndex]) {
            endIndex = midleIndex-1;
        }

    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ As long as your array is sorted... \$\endgroup\$ – RobAu Feb 23 '17 at 11:38
  • \$\begingroup\$ Yes the array is sorted \$\endgroup\$ – M.Blaiz Feb 23 '17 at 11:39
  • 8
    \$\begingroup\$ Your calculation of the middle index may overflow. Consider middleIndex = start + (end - start) / 2 or approach I recently found out about middleIndex = (start + end) >>> 1; \$\endgroup\$ – Shadov Feb 23 '17 at 12:44
  • 2
    \$\begingroup\$ @Whatzs why can't the bit-shift implementation overflow? \$\endgroup\$ – Cruncher Feb 23 '17 at 18:04
  • 2
    \$\begingroup\$ @AndersTornblad According to §15.19. Shift Operators in The Java® Language Specification >>> (unsigned right shift) always zero-extends. \$\endgroup\$ – Johnbot Feb 24 '17 at 8:56
12
\$\begingroup\$

It is a neat implementation.

I like the potential performance. You don't use recursive calls, so this saves some calls.

I don't like (this is a personal preference) endless loops with returns.

Beware that it only works on sorted arrays, and there is no JavaDoc explaining this. This might lead to incorrect use of your method.

And you should always cover the edge cases.

If you input an empty array, you will end up with:

  Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
\$\endgroup\$
  • 2
    \$\begingroup\$ Please do not add, remove, or edit code in a question after you've received an answer. The site policy is explained in What to do when someone answers. \$\endgroup\$ – RobAu Feb 23 '17 at 11:50
  • 1
    \$\begingroup\$ Oh, sorry for that, I'm not aware of that policy. \$\endgroup\$ – M.Blaiz Feb 23 '17 at 11:53
  • 4
    \$\begingroup\$ @SamusArin I sympathize with RobAu. It hurts me inside every time I write a while(true) loop. But I do it anyway because it is the cleanest solution sometimes. The problem is that you can't determine the exit condition of the loop by looking at the declaration of the loop. \$\endgroup\$ – Cruncher Feb 23 '17 at 18:08
  • 1
    \$\begingroup\$ @SamusArin It is almost always possible to put a conditional in it, that makes you program better and more readable. See for example the while loop in the answer of rolfl \$\endgroup\$ – RobAu Feb 24 '17 at 7:49
  • 1
    \$\begingroup\$ @SamusArin I use the phrase "self-documenting code" at least a couple times a week. My colleagues think it's just an excuse to not write comments... \$\endgroup\$ – Cruncher Feb 24 '17 at 16:20
10
\$\begingroup\$

There is two unusualities about this method:

  • You're returning a boolean (which conveys only minimal information)
  • You're using infinite-loops instead of a terminating loop.

The first part can be easily remedied. Instead of returning a boolean, you should return the index where you found the element. Note that Arrays.binarySearch (the standard function) does it exactly that way. It will return a negative value in case the element could not be found in the given array.

The infinite loop you have there can be fixed in two different ways. Either by using recursion (which can be dangerous) or by using a properly limited loop. The simplest condition I can think of for the loop to continue is: while (startIndex != endIndex) {

Other improvements include the following:

  • Declare variables on a separate line to ease readability (and initialization)
  • correct the typo in midleIndex (should be middleIndex)
  • Notice that middleIndex only is needed inside the loop, so you might as well declare it inside. The JIT should be smart enough to not reallocate this every time
  • Instead of chaining if-statements, you should consider using else, especially in pairwise exclusive statements.

    The moment you reach if (valueToFind > arrayToScan[middleIndex]) you already know that the value at middleIndex is not the one you've been looking for. And if it isn't larger it automatically is smaller. Accordingly the if (valueToFind < arrayToScan[middleIndex]) doesn't provide you with any informational benefit. Instead you can just use else.

\$\endgroup\$
  • 7
    \$\begingroup\$ Pedantic issue - Arrays.binarySearch(...) does not only return -1. It returns -i - 1 where i is the index of where the value should be inserted if you add it in to the array. \$\endgroup\$ – rolfl Feb 23 '17 at 12:21
  • \$\begingroup\$ @rolfl TIL .. that's kind of nice, actually :) \$\endgroup\$ – Vogel612 Feb 23 '17 at 12:33
  • \$\begingroup\$ Thanx, I didn't put attention that I only need an else. Also thanx for other valid points \$\endgroup\$ – M.Blaiz Feb 23 '17 at 13:19
  • \$\begingroup\$ @rolfl I was about to say why use -i-1 instead of just -i. But of course it matters in the case of i=0. That's very useful to know though! \$\endgroup\$ – Cruncher Feb 23 '17 at 18:13
  • \$\begingroup\$ Well it returns ~i, which you can also write as -i - 1 if you're scared of bitwise operations, but I find ~i simpler to reason about \$\endgroup\$ – harold Feb 25 '17 at 11:34
7
\$\begingroup\$

You have some bugs in your code, they are hard to spot. In many cases, you won't see this bug, but it breaks down to the concept of your "end-index". You set up your end-index to be the length of the array, but then later, when end-index is set to the middle, it is calculated as middleIndex - 1 instead of just being set to middleIndex. I corrected that off-by-1 in my copy of your code, but it still had some issues that I decided I would not try to debug.

This is an "off-by-1" error, and it's hard to spot. See: https://en.wikipedia.org/wiki/Off-by-one_error

In addition, there's a very remote chance that your code will be used with large input arrays (like, very large inputs, more than 2^30 elements...) in which case your calcualtion for the mid-point may fail: (startIndex + endIndex) / 2; because startIndex + endIndex could overflow to become a negative number, which is not what you want. The better solution is to use startIndex + (endIndex - startIndex) / 2 which will never overflow: https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html

Now, your method is called find which I expect to return a location, not a boolean. I understand that you only need to do a check to see if the value is present, so I would rename the method to exists.

Finally, I don't have a problem with infinite loops like you have, but I wonder whether reducing this to a for-loop isn't better anyway....

I wrote some code to test this, and came up with:

public static boolean exists(int[] arrayToScan, int valueToFind) {
    for (int startIndex = 0, endIndex = arrayToScan.length, middleIndex = endIndex / 2;
            startIndex < endIndex;
            middleIndex = startIndex + (endIndex - startIndex) / 2) {
        if (arrayToScan[middleIndex] == valueToFind) {
            return true;
        }
        if (valueToFind > arrayToScan[middleIndex]) {
            startIndex = middleIndex + 1;
        } else {
            endIndex = middleIndex;
        }
    }
    return false;
}

Note that I use comma-separated terms in the for-loop init. This is not a common thing to do, and has it's own concerns, but it structures the loop appropriately.

I have put together a test case that hammers your method, and my method, and it shows how your first bug appears. See the code running on ideone: https://ideone.com/wEgoCv and look for "false" values from the find method (e.g. searching for 0 in the array [0, 1].... ;-))

Edit: Restructured as a while-loop again, but with the same setup/conditionals:

public static boolean exists(int[] arrayToScan, int valueToFind) {
    int startIndex = 0;
    int endIndex = arrayToScan.length;
    while (startIndex < endIndex) {
        int middleIndex = startIndex + (endIndex - startIndex) / 2;
        if (arrayToScan[middleIndex] == valueToFind) {
            return true;
        }
        if (valueToFind > arrayToScan[middleIndex]) {
            startIndex = middleIndex + 1;
        } else {
            endIndex = middleIndex;
        }
    }
    return false;
}
\$\endgroup\$
  • \$\begingroup\$ I never thought that it's possible with only a for-loop, also, as you stated, the off-by-1 is hard to spot. thanx for your feedback \$\endgroup\$ – M.Blaiz Feb 23 '17 at 13:20
  • 1
    \$\begingroup\$ @M.Blaiz A for loop is really just syntactic sugar for a common form of while loop. That is a for(init ; condition ; step) {...} loop is identical to init; while(condition) {... step;} Converting from the while loop to a for loop, you just need to shoehorn some of the logic from the while loop to fit this form \$\endgroup\$ – Cruncher Feb 23 '17 at 18:18
  • 1
    \$\begingroup\$ That being said, I personally find the for-loop to be far less readable here \$\endgroup\$ – Cruncher Feb 23 '17 at 18:19
  • 3
    \$\begingroup\$ @Cruncher - taking your comments to heart, I restructured it back in to a for loop, and I can see the benefit of the while loop too. I hang around with a bunch of old-school folk (maybe I am one of them), and we commonly use compound for-loop initializers. It may be a bad habit. \$\endgroup\$ – rolfl Feb 23 '17 at 18:25
1
\$\begingroup\$

I would suggest another minor correction, which is more a matter of semantics. Since your endIndex is the index that points to the last element of your array, it should be endIndex = arrayToScan.length - 1 since length returns the size of the array and not the position of the last element.

\$\endgroup\$
  • \$\begingroup\$ Well put my friend, never had the words to describe that scenario until now :). \$\endgroup\$ – samis Feb 24 '17 at 16:09
1
\$\begingroup\$

You make two assumptions:

  1. The array is sorted.

  2. The value being searched for is in fact within the value set.

An assumption on my part: If the value is outside the value set, then return either the lower or the upper value as appropriate.

If parmvalue <= array.lowervalue then
   return array.lowervalue
else
   if parmvalue => array.maxvalue then
      return array.maxvalue
   enif
endif

That trims any search outside the array with no looping

Staying out of the other "opinion" being expressed.

\$\endgroup\$
1
\$\begingroup\$

I like to sometimes use a more systematic mathematical notation for these such algorithms as it really helps to make the syntax more self explanatory.

So, if instead the original problem was posed in a more succinct notation like:

public static boolean find(int[] ary, int val) {
    int i = 0, n = ary.length, m;
    while( true ) {
        m = (i + n) / 2;
        if( ary[m] == val ) {
            return true;
        }
        if( i >= n || m == 0 || m == ary.length - 1 ) {
            return false;
        }
        if( val > ary[m] ) {
            i = m + 1;
        }
        if( val < ary[m] ) {
            n = m - 1;
        }           
    }
}

Then when refactoring, it is much easier to compare and evaluate the main differences of the algorithms at a glance. Take for example this answer from above:

public static boolean exists(int[] ary, int val) {
    for (int i = 0, n = ary.length, m = n / 2;
            i < n;
            m = i + (n - i) / 2) {
        if (ary[m] == val) {
            return true;
        }
        if (val > ary[m]) {
            i = m + 1;
        } else {
            n = m;
        }
    }
    return false;
}

Note that I use comma-separated terms in the for-loop init. This is not a common thing to do, and has it's own concerns, but it structures the loop appropriately.

I have put together a test case that hammers your method, and my method, and it shows how your first bug appears. See the code running on ideone: https://ideone.com/wEgoCv and look for "false" values from the find method (e.g. searching for 0 in the array [0, 1].... ;-))

Edit: Restructured as a while-loop again, but with the same setup/conditionals:

public static boolean exists(int[] ary, int val) {
    int i = 0;
    int n = ary.length;
    int m = n / 2;
    while (i < n) {
        if (ary[m] == val) {
            return true;
        }
        if (val > ary[m]) {
            i = m + 1;
        } else {
            n = m;
        }
        m = i + (n - i) / 2
    }
    return false;
}
\$\endgroup\$
  • \$\begingroup\$ ... and what Enigma Maitreya say's below ... \$\endgroup\$ – samis Feb 23 '17 at 19:32
0
\$\begingroup\$
endIndex = arrayToScan.length - 1

if (startIndex >= endIndex || midleIndex == 0 || midleIndex == arrayToScan.length - 1) {
    return false;
}

you will get there with

if (startIndex >= endIndex) {
    return false;
} 

can just put the above in a while

can deal with = in an else

Why not return the actual index?
You can return the index for the same cost
You just are using a lot more code than you need to

public static int indexOf(int[] a, int key) {
    int lo = 0;
    int hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if      (key < a[mid]) hi = mid - 1;
        else if (key > a[mid]) lo = mid + 1;
        else return mid;
    }
    return -1;
}
\$\endgroup\$
  • \$\begingroup\$ Compared to edited version of @rolfl setting hi=mid-1 required that (lo<=hi) ? \$\endgroup\$ – M.Blaiz Feb 24 '17 at 10:15
  • \$\begingroup\$ Not sure what you are asking. Easy enough to test. \$\endgroup\$ – paparazzo Feb 24 '17 at 13:36
0
\$\begingroup\$

Rewriting of existing API is always dangerous. Better use existing Arrays.binarySearch. I would suggest the simplest and most reliable implementation:

public static boolean find(int[] arrayToScan, int valueToFind) {
    return Arrays.binarySearch(arrayToScan, valueToFind) > -1;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.