JIYIK CN >

Hey Java programmers, if you want to implement binary search in Java and looking for iterative and recursive binary search algorithms, then you have come to the right place. Today I am going to teach you an important algorithm. In computer science, binary search or semi-interval search is a divide and conquer algorithm that locates the position of an item in a sorted array. Binary search works by comparing the input value with the middle element of the array. The comparison determines whether the element is equal to the input, less than the input, or greater than the input.

When the compared element is equal to the input, the search stops and the position of the element is usually returned. If the element is not equal to the input, a comparison is performed to determine whether the input is less than or greater than the element.

Depending on what algorithm it is it then starts over but only searches the top or bottom subset of the array elements. If the input is not in the array the algorithm will usually output a unique value to indicate this.

A binary search algorithm typically halves the number of items to be examined with each successive iteration, thereby locating a given item (or determining its absence) in logarithmic time.

Binary search is a divide and conquer search algorithm. It works by splitting the input set into two halves and then applying the algorithm and repeating the same steps until the work is done.

Java Binary Search Without Recursion It is also very intuitive and full of helpful diagrams that explain the concepts very well. For example, in the diagram above, we can see that linear search gets slower and slower as the number of elements increases, but binary search does not. For example, with 4 billion items, binary search only needs 32 guesses

Binary Search Example in Java without Recursion

The algorithm is implemented recursively. Also, an interesting fact about binary search implementation in Java is that Joshua Blochjava.util.Arrays , the author of the famous Effective Java book , implemented binary search in .

import java.util.Arrays;

/**
 * 实现二进制搜索的 Java 程序。
 */
public class Main {
    public static void main(String args[]) {
        int[] list = new int[]{23, 43, 31, 12};
        int number = 12;
        Arrays.sort(list);
        System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
        binarySearch(list, 12);
        System.out.printf("Binary Search %d in integer array %s %n", 43, Arrays.toString(list));
        binarySearch(list, 43);
        list = new int[]{123, 243, 331, 1298};
        number = 331;
        Arrays.sort(list);
        System.out.printf("Binary Search %d in integer array %s %n", number, Arrays.toString(list));
        binarySearch(list, 331);
        System.out.printf("Binary Search %d in integer array %s %n", 331, Arrays.toString(list));
        binarySearch(list, 1333);
        Arrays.sort(list);
        int index = Arrays.binarySearch(list, 3);
    }

    /**
     * 在 Java 中的排序数组中执行二分搜索
     * @param input
     * @param number
     * @return 元素在数组中的位置
     */
    public static void binarySearch(int[] input, int number) {
        int first = 0;
        int last = input.length - 1;
        int middle = (first + last) / 2;
        while (first <= last) {
            if ( input[middle] < number){
                first = middle + 1;
            } else if (input[middle] == number) {
                System.out.printf(number + " found at location %d %n", middle);
                break;
            } else {
                last = middle - 1;
            }
            middle = (first + last) / 2;
        } if ( first > last){
            System.out.println(number + " is not present in the list.\n");
        }
    }
}

The execution results are as follows

That's all about how to implement a binary search algorithm in Java without recursion. As with any recursive algorithm, this code does not use any loops like while, , foror do-while. Ideally, we wouldn't need to write code for binary search for day-to-day tasks because the Java library already has a , binarySearch(), or . But knowing how to write these algorithms helps in interviews.