# Developers Planet

MrTumble February 2016

### Binary Search Program

The code is a simple binary search program. I tried tracing the program but it only made me more confused. I can't figure out why the nested if has data, min, midpoint - 1, & target vs. the bottom else if statement has data, midpoint + 1, max, target.

``````public static boolean binarySearch(int[] data, int min, int max, int target){
boolean found = false;
int midpoint = (min + max) / 2;  // determine the midpoint

if (data[midpoint] == target)
found = true;

else if (data[midpoint] > target)
{
if (min <= midpoint - 1)
found = binarySearch(data, min, midpoint - 1, target);
}

else if (midpoint + 1 <= max)
found = binarySearch(data, midpoint + 1, max, target);

return found;
}
``````

cricket_007 February 2016

Binary search searches the left half `(min... mid-1)` and the right half `(mid+1...max)` recursively.

You are checking `mid` against `target`, so that is why it isn't included in that range.

You really should have a base-case for `if (min >= max) return false;` to prevent going out of bounds of the array.

Here is a cleaner implementation as I find it easier to understand

``````public static boolean binSearch(int[] data, int target) {
return _binSearch(data, target, 0, data.length);
}

private static boolean _binSearch(int[] data, int target, int low, int high) {
int mid = (low + high) / 2;

if (low >= high) return false;

if (data[mid] == target) return true;

boolean foundLeft = _binSearch(data, target, low, mid);
boolean foundRight = !foundLeft && _binSearch(data, target, mid+1, high);

return foundLeft || foundRight;
}
``````

RYS221 February 2016

The array data is already sorted from smallest to largest

Therefore it finds if the value at the midpoint is greater than the target, then the target would appear in the values before midpoint. So we recursively call the method only on the left of the midpoint i.e. all the values from the min till the value before the midpoint.

Similarly if the midpoint is less than the target, the target could be found after the midpoint, therefore we recursively call the method only on the right of the midpoint i.e. all the values from the value after the midpoint to the end.

Each time time we don't include the midpoint as that is checked in the line

`````` if (data[midpoint] == target)
``````

e.g Array 3 6 8 10 13 14 20. target = 14 the midpoint would be = 10 9index 4). Checking target and midpoint, we'd see that the target is greater than the midpoint and falls on the right. So we now check for target in 13 14 20 --- from midpoint+1 (index 5) till the end. The midpoint would be 14. And the above if statement would return true.

Neuron February 2016

You divide your data into a half smaller than `midpoint`, with a range `(min, mid-1)` and bigger than `midpoint`, with a range `(mid+1, max)`.

if you have an input of `{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}`, and `min = 0; max= 10`, then

``````int midpoint = (0 + 10) / 2; // which is 5
``````

Iff `data[midpoint]` is not what you were looking for, need need to look for everything left or right (but not `midpoint` itself, thats why there is a `-1` and a `+1` in there..)

So the range for the left half is `(0, 4)` and the range for the right half is `(6, 10)`.

If you are looking for, lets say 12, we'd go left, because `data[midpoint] == 13 && 13 > 12`:

``````int midpoint = (0 + 4) / 2; // which is 2
``````

since `data[2] < 10`, we'd go right, with `min = 3; max = 4;` and so on..

MaxZoom February 2016

It seems the code incorrectly compares the current `midpoint` with the `min` and `max` index. Instead

``````if (min <= midpoint - 1)
:
else if (midpoint + 1 <= max)
``````

it should use

``````if (min < midpoint - 1)
:
else if (midpoint + 1 < max)
``````

Try the below attempt to correct it:

``````public static boolean binarySearch(int[] data, int min, int max, int target){
if (max > min) {
int midpoint = (min + max) / 2;  // determine the midpoint

if (data[midpoint] == target) {
return true;
}

if (data[midpoint] > target) { // use lower half
return  binarySearch(data, min, midpoint-1, target);
}
else { // use upper half
return  binarySearch(data, midpoint+1, max, target);
}
}
return false;
}
``````

See DEMO

#### Post Status

Asked in February 2016
Viewed 3,028 times
Voted 14