# Simple binary seach

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;
}

}
}

• As long as your array is sorted... Feb 23, 2017 at 11:38
• Yes the array is sorted Feb 23, 2017 at 11:39
• 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; Feb 23, 2017 at 12:44
• @Whatzs why can't the bit-shift implementation overflow? Feb 23, 2017 at 18:04
• @AndersTornblad According to §15.19. Shift Operators in The Java® Language Specification >>> (unsigned right shift) always zero-extends. Feb 24, 2017 at 8:56

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

• 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. Feb 23, 2017 at 11:50
• Oh, sorry for that, I'm not aware of that policy. Feb 23, 2017 at 11:53
• @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. Feb 23, 2017 at 18:08
• @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 Feb 24, 2017 at 7:49
• @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... Feb 24, 2017 at 16:20

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

• 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. Feb 23, 2017 at 12:21
• @rolfl TIL .. that's kind of nice, actually :) Feb 23, 2017 at 12:33
• Thanx, I didn't put attention that I only need an else. Also thanx for other valid points Feb 23, 2017 at 13:19
• @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! Feb 23, 2017 at 18:13
• 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 Feb 25, 2017 at 11:34

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;
}

• 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 Feb 23, 2017 at 13:20
• @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 Feb 23, 2017 at 18:18
• That being said, I personally find the for-loop to be far less readable here Feb 23, 2017 at 18:19
• @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. Feb 23, 2017 at 18:25

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.

• Well put my friend, never had the words to describe that scenario until now :). Feb 24, 2017 at 16:09

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.

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;
}

• ... and what Enigma Maitreya say's below ... Feb 23, 2017 at 19:32
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;
}

• Compared to edited version of @rolfl setting hi=mid-1 required that (lo<=hi) ? Feb 24, 2017 at 10:15
• Not sure what you are asking. Easy enough to test. Feb 24, 2017 at 13:36

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;
}