CODEWITHSUNDEEP
javabinary-search
user7553755
user7553755

Reputation:

Error in binary search Java

I've been given this binary search to figure out what's wrong with it. There is a line commented out and so far the only thing I can think of is removing that line as I don't think it is needed. Apart from that, I cannot think of anything missing - is there something really obvious that is wrong? 

public boolean search(int val) {
    int low = 0;
    int high = size-1;
    int middle = -1;
    boolean found = false;
    while (!found && low < high) {
        middle = low + (high-low)/2;
        if (a[middle] == val)
           found = true;
        else if (a[middle] < val)
           low = middle + 1;
        else // (a[middle] > val)
           high = middle - 1;
    }
    return found;
}

Upvotes: 1

Views: 168

Answers (3)

OldCurmudgeon
OldCurmudgeon

Reputation: 65811

Take the array you are search to be [1,2].

Walk the code:

Start: low = 0, high = 1. Step1: middle = 0 - no match (1 < 2) so low = 1. Loop check - low < high? NO - stop searching.

Upvotes: 0

Migwel
Migwel

Reputation: 143

Let's take the case when you have 2 values in your array: [0, 1] and you look for value 1. Let's run the code:

int low = 0;
int high = size-1; // high = 1
int middle = -1;
boolean found = false;
while (!found && low < high) {
    middle = low + (high-low)/2; // middle = 0 + (1-0) / 2 = 0
    if (a[middle] == val) // FALSE (because a[0] = 0)
       found = true;
    else if (a[middle] < val) // TRUE (because a[0] = 0 and 0 < 1)
       low = middle + 1;  // low = 0 + 1 = 1
    else // (a[middle] > val)
       high = middle - 1;
}
return found;

Because low = 1, you get out of the loop since you have a condition low < high and your return false, even though 1 is present in your array.

The problem comes from the fact that middle = low + (high-low)/2; uses int and will be rounded down.

Upvotes: 1

GhostCat
GhostCat

Reputation: 140457

Lets go in and make your code easier to read...

middle = low + (high-low)/2;
if (a[middle] == val) {
  found = true;
  break;
}

if (a[middle] < val) {
  low = middle + 1; 
} else { 
  high = middle - 1;
}

I think now it becomes clearer, what that comment is really saying - it simply expresses that this is the case when a[middle] > val.

Upvotes: 0

Related Questions