Binary Search in Java made easy

First of all, binary search has nothing to do with 0's and 1's. I always think of that when I think of binary search. It is called binary search because it continuously splits up an ordered list in two. Think of a loaf of bread. There are 10 pieces. I want to find the 4th piece. I am going to initial guess at the middle piece, bread slice number 5. I am too high, but I know that the second half of the loaf is all too high. So I will set the max to be 5-1, or 4. Now I will guess it is in the middle of that chunk at piece 2. I am too low but I know that it isn't in the first half of these either so I will set the minimum number to 2. Repeat this process until you find the piece of bread. Try doing it in real life.

The psuedocode for binary search is pretty basic. Here it is:

1. Set min = 0 and max = n-1 (where n is the index of the last item in the list)
2. Check if max < min (this signals that the number is not in the list)
3. Take a guess. Make the guess at (max + min) / 2
4. Check if the guess is right. If it is, you're good! If not:
5. If your guess was less than the target, set your min value to your guess + 1 (get rid of a half of bread)
6. If your guess was greater than the target, set your max to your guess - 1
7. Repeat step 2.

That's all there is to it. Here is a working example in Java. The list contains all the even numbers up to 20. So this could be used to determine if a number is even or not. If it is found, the number is even. If not, the number is odd. (Zero is not included).

Open Eclipse and go to File -> New ->Project and select Java project. Right click on the src folder and add a class named BinSearch,java. Make sure to check add main args in the options or paste the code exactly as follows. Right click and select run to run it.


public class BinSearch {

    public static void main(String[] args) {
   
        int[] x = {2,4,6,8,10,12,14,16,18,20};
        int min = 0;
        int max = x.length - 1;
        int target = 6;
        int guess = 0;
        boolean searching = true;
        while(searching)
        {
            if(max < min)
            {
                System.out.println("Not found");
                searching = false;
            }
            guess = (int)Math.floor((max + min) / 2);
          
            if(x[guess] == target)
            {
                System.out.println("Found");
                searching = false;
            }
            if(x[guess] < target)
                min = guess + 1;
            else
                max = guess - 1;
          
        }
   
    }
}

Here is a graphic showing the process visually: