Issue with Binarysearch-Algorithm code

Question

So I've been looking for my mistake in this code for 10-20 minutes, but I still couldn't find any mistake. However I found out (after finally adding a systemout) that somethings wrong with my "middle" Integer because it's < than the lowest number (start)

Any help is appreciated!

Here's the code:

public class BinaereSuche {

public static int intList[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};


public static int bineareSuche(int number){
    int start = 0;
    int end = intList.length -1;
    boolean found = false;

    while(found == false){ 
        int middle = (end - start) / 2; 

        if(number > intList[middle]){ 
            start = middle + 1;
        }else if(number < intList[middle]){ 
            end = middle - 1;
        }else
            return middle;
        found = true;
        System.out.println(intList[start] + " <--> " + intList[end] + " => " + intList[middle]);
    } return -1;
}

public static void main(String[] args) {
    System.out.println(bineareSuche(32));
  }
}

The sysout gives me32 <--> 512 => 16 -1 where as 32 is the start number, 512 is the end number and 16 is the middle number between 512 and 32 which is obviously wrong.

p.s. I have been looking for answeres here on SO but still couldn't help find my problem -- If anyone is curious about how it works (if you don't already know): Here's a picture

Hint: there is an unconditional found=true in your while loop. So the loop will never execute more than once. — WhiteViking
– WhiteViking, Commented Nov 1, 2015 at 21:42

Peter de Rivaz · Accepted Answer · 2015-11-01 21:33:28Z

1

I think this line is wrong:

int middle = (end - start) / 2;

try:

int middle = start + (end - start) / 2;

Consider end=10, start = 9. Your approach will calculate middle = 0.

answered Nov 1, 2015 at 21:33

Peter de Rivaz

33.6k4 gold badges51 silver badges80 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

WhiteViking Over a year ago

It's not the only bug. Try searching for another value than 32. (See my comment above.)

moon Over a year ago

@WhiteViking Oh yea, sorry forgot to reply after I've changed the code. Even though I didn't quite understand why the boolean changed to true because it shouldn't have changed (?), I deleted the boolean and changed that to: ´while(start <= end){...}´ and it perfectly worked.

Collectives™ on Stack Overflow

Issue with Binarysearch-Algorithm code

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related