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

Answers


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
Answered 4 times

Search




Leave an answer