Binary search java

1. Overview

In this article, we will learn about the Binary search implementation in Java. To learn more about data structures, refer to our articles.

2. Binary search

A Binary search is an algorithm that requires its input as a sorted list of elements. If an element you’re looking for is in that list, the binary search returns the position where it’s located. Otherwise, the binary search returns null.

Here’s an example of how binary search works.

Assume you have a list of elements starting from 1 to 100. Now, just think of a number between 1 and 100.

Try to guess the number in the fewest tries possible. With every guess, I’ll tell you if your guess is too low, too high, or correct. Suppose you guess like this: 1, 2, 3, 4 …. Here’s how it would go.

In this type of search, with each guess, you’re eliminating only one number. If the number was 99, it could take you 99 guesses to get there.

2.1. Binary search concept

Let’s start with 50.

Too low, but you just eliminated half the numbers. Now you know that 1–50 were all too low. Next guess: 75.

Too high, but again you cut down half the remaining numbers. With binary search, you guess the middle number and eliminate half the remaining numbers every time. Next is 63 (halfway between 50 and 75).

Whatever number it could be, you can guess at a maximum of seven guesses (worst case) because you eliminate so many numbers with every guess.

100 -> 50 -> 25 -> 13 -> 7 -> 4 -> 2 -> 1

For any list of n, binary search will take log2 n steps to run in the worst case, whereas a simple search will take n steps.

For example, a list of 100 would take log2 100 = 7 (2 * 2 * 2 * 2 * 2 * 2 * 2).

2.2. Binary search in Java example

At first, take the length of the list.

low = 0
high = len(list) - 1

Each time, divide the range by 2.

mid = (low + high) 
guess = list[mid]

@Test
    void binarySearchExample() {
        int[] list = IntStream.range(0, 10).toArray();
        int value = 9;
        System.out.println(binarySearch(list, value));

    }

    private int binarySearch(int[] list, int value) {
        int low = 0;
        int high = list.length - 1;

        System.out.println(high);
        int pos = -1;
        while (low <= high) {
            pos = (int) Math.ceil((float) (low + high) / 2);
            System.out.println(pos);
            if (value < list[pos]) { 
                high = pos - 1; 
            } else if (value > list[pos]) { 
                low = pos + 1; 
            } else {
                return pos; 
            }
        }
        return pos;
    }

Above is the full working code in Java.

You can use the below code to find the value among a list of string objects.

@Test
    void binarySearchStrExample() {
        List<String> names = Arrays.asList("Abram", "Adam", "Bob", "Chris", "John", "Kevin");
        String value = "John";
        System.out.println(binarySearchStr(names, value));

    }

    private int binarySearchStr(List<String> list, String value) {
        int low = 0;
        int high = list.size() - 1;

        System.out.println(high);
        int pos = -1;
        while (low <= high) {
            int mid = (int) Math.ceil((float) (low + high) / 2);
            int x = value.compareTo(list.get(mid)); 
            System.out.println(mid);
            if (x < 0) { 
                high = mid - 1;
            } else if (x > 0) {
                low = mid + 1;
            } else if (value.equalsIgnoreCase(list.get(mid))){
                return mid;
            }
        }
        return pos;
    }

3. Conclusion

To sum up, we have seen the binary search algorithm in Java. You can find code samples in our GitHub repository.