Binary Search Java example. Easy solution.

In Java, binary search is the preferable solution than the linear search. It is a better solution from a complexity point of view. Because in comparison with the linear search, you need much fewer iterations to find the needed element.

The main idea of the binary search.

The main idea here is to make a pointer that will show the middle of the array list. Then we need to check if the searched element value less or more than the middle pointer. If it is less, we are moving the pointer and the right end to the array list’s left side. In case the value is higher than the pointer, we are moving the middle pointer and the left end to the right side. As a result, we divide our array list in half. Then the half result we divide in half again. We should repeat that process until we find the needed element. One important moment is that we need to sort the list first. Let’s try to discuss every step in detail.

Example explanation? The best solution in Java.

Step-by-step binary search solution. Code example with pictures and diagram explanations below:

Part one. We need to prepare all pointers and start looping:

• Setup two pointers We need those pointers to cut the needed part to continue the search. It is left pointer and right pointer;

//Start point of search
        int leftPointer = 0;
//End point of search
        int rightPointer = array.length - 1;

• Set the result variable. By default, I would set it to minus one. If, after running the algorithm, the result is still minus one. That means we didn’t find anything. Otherwise, it will return the index of the needed element;

//Value we are looking for
        int searchedItem = 12;

• Start “while” loop. Looping until the start pointer is less or equal to the end pointer. With each iteration, we should move both pointers to each other, and at the end, pointers should face the needed element;

//Divide and conquer principe looping
        while (leftPointer <= rightPointer)

• With the help of the formula, we need to set the middle value. This pointer will divide our array in the middle and will help us make an important decision. To move it to the left or the right. This pointer will find the result; 

//Setting the middle of the array
            int middlePointer = (leftPointer + rightPointer) / 2;

Part two. Implement three conditions that help us find the element:

• If the searched value less than the middle. Since the array list is sorted, it means that the searched value is before the middle pointer. That’s why we are moving our right pointer to the middle and run one more iteration;
• If the search value more than the middle pointer value. Again, since the array list is sorted, the searched value is going after the middle pointer. That’s why we should move the left pointer to the middle and run iteration one more time;

 //If searched item less that middle
            if (searchedItem < array[middlePointer]) {
//Moving search part to left of the middle by setting end point to mid - 1
                rightPointer = middlePointer - 1;
            } else {
//If searched item more than middle
//Moving search part to right of the middle by setting start point to mid + 1
                leftPointer = middlePointer + 1;
            }

• If the middle pointer is equal to the needed value. Set the result value to the middle pointer value index;

//If middle value the same as search we have found the item
            if (array[middlePointer] == searchedItem) {
                Log.d("arrayList", "---> " + middlePointer);
                return;
            }

• As a result, we will move pointers until we find the needed element and return its index. Otherwise, we return minus one;

Animation:

Full Schema:

Full code solution:

private void binarySearch() {
        //Creating array of int
        int[] array = new int[]{2,5,6,8,9,12};

        //Start point of search
        int leftPointer = 0;
        //End point of search
        int rightPointer = array.length - 1;

        //Value we are looking for
        int searchedItem = 12;

        //Result index we are looking for
        int result = -1;
        //Divide and conquer principe looping
        while (leftPointer <= rightPointer) {
 //Setting the middle of the array
            int middlePointer = (leftPointer + rightPointer) / 2;

//If middle value the same as search we have found the item
            if (array[middlePointer] == searchedItem) {
                Log.d("arrayList", "---> " + middlePointer);
                return;
            }

            //If searched item less that middle
            if (searchedItem < array[middlePointer]) {
//Moving search part to left of the middle by setting end point to mid - 1
                rightPointer = middlePointer - 1;
            } else {
                //If searched item more than middle
//Moving search part to right of the middle by setting start point to mid + 1
                leftPointer = middlePointer + 1;
            }

        }

        Log.d("arrayList", "Nothing have been found");
    }

In this article, I explained the principles of the binary search Java.

Full code and more examples in my facebook group.

Useful links:

• Selection Sort Example
• Bubble Sort
• Example of Insertion Sort
• Example of Linear Search