Skip to content

Yet another programming solutions log

Sample bits from programming for the future generations.

Technologies Technologies
  • Algorithms and Data Structures
  • Java Tutorials
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Spock Framework Tutorial
  • Spring Framework
  • Bash Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Developer’s Tools
  • Productivity
  • About
Expand Search Form

Java binary search

farenda 2015-06-30 0

Problem:

Java binary search is very fast way to find an element in a sorted collection of elements or find a place where it should be inserted. In this tutorial you will learn how to effectively use binary search in Java!

Solution:

Binary search is fundamental searching algorithm and it’s very fast. It works only with sorted collections in ascending order, so do it first if needed.

As always, Java has binary search algorithm implemented in its vast JDK API. It’s in java.util.Collections. The following example demonstrates how to use int binarySearch(List list, T key) version:

package com.farenda.java;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class CollectionsBinarySearch {

    public static void main(String[] args) {
        String s = "Binary search in Java";
        // let's remove the spaces
        s = s.replaceAll(" ", "");

        List<String> items = Arrays.asList(s.split(""));
        System.out.println("Unsorted items: " + items);

        // Search in unsorted list gives unpredictable result:
        int idx = Collections.binarySearch(items, "i");
        System.out.println("Found 'i' at index: " + idx);

        // Items must be sorted in ascending order:
        Collections.sort(items);
        System.out.println("Sorted items: " + items);

        // Search in a sorted list:
        idx = Collections.binarySearch(items, "i");
        System.out.println("Found 'i' at index: " + idx);

        // Find insertion point for non existing item:
        idx = Collections.binarySearch(items, "d");
        System.out.println("'d' can be inserted at: " + -(idx+1));
    }
}

Running the above Java code prints the following output:

Unsorted items: [B, i, n, a, r, y, s, e, a, r, c, h, i, n, J, a, v, a]
Found 'i' at index: 12
Sorted items: [B, J, a, a, a, a, c, e, h, i, i, n, n, r, r, s, v, y]
Found 'i' at index: 10
'd' can be inserted at: 7

As you can see using binary search on unsorted list gives a funky result – found ‘i’ at 12, but there’s another one at index 2, which is not even close!

Another interesting thing is that Collections.binarySearch returns index of found item or (-insertionPoint – 1) when for not found item. It has to be this way, because indexes from 0 to length of string are used for found items, and only negative numbers are freely available to indicate where an element could be inserted. So we find the index by reversing the equation: -(insertionPoint +1).

Keep in mind that elements in the list have to be mutually comparable, else ClassCastException will be thrown!

In the next tutorial we’ll show how to use binarySeach(List, T, Comparator) version, which allows to compare items using own java.util.Comparator, so stay tuned! :-)

Share with the World!
Categories Java Tags algorithms, java-collections
Previous: Java Deque Stack Queue
Next: Java binary search comparator

Recent Posts

  • Java 8 Date Time concepts
  • Maven dependency to local JAR
  • Caesar cipher in Java
  • Java casting trick
  • Java 8 flatMap practical example
  • Linked List – remove element
  • Linked List – insert element at position
  • Linked List add element at the end
  • Create Java Streams
  • Floyd Cycle detection in Java

Pages

  • About Farenda
  • Algorithms and Data Structures
  • Bash Tutorial
  • Bean Validation Tutorial
  • Clojure Tutorial
  • Design Patterns
  • Java 8 Streams and Lambda Expressions Tutorial
  • Java Basics Tutorial
  • Java Collections Tutorial
  • Java Concurrency Tutorial
  • Java IO Tutorial
  • Java Tutorials
  • Java Util Tutorial
  • Java XML Tutorial
  • JUnit Tutorial
  • MongoDB Tutorial
  • Quartz Scheduler Tutorial
  • Software Developer’s Tools
  • Spock Framework Tutorial
  • Spring Framework

Tags

algorithms bash bean-validation books clojure design-patterns embedmongo exercises git gof gradle groovy hateoas hsqldb i18n java java-basics java-collections java-concurrency java-io java-lang java-time java-util java-xml java8 java8-files junit linux lists log4j logging maven mongodb performance quartz refactoring regex rest slf4j solid spring spring-boot spring-core sql unit-tests

Yet another programming solutions log © 2021

sponsored
We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.Ok