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 comparator

farenda 2015-07-01 0

Problem:

Java Binary Search with Comparator is very flexible method to search for elements of any type. In this tutorial you will learn how to use binary search in Java with own Comparator!

Solution:

In previous, Java Binary Search tutorial, we’ve shown how to use binary search with Comparable items. In this one we’ll show how to use Collections.binarySearch(), that takes also java.util.Comparator as a parameter and allows to search even on not mutually comparable elements!

Here’s a Java class that doesn’t implement java.util.Comparable interface, hence it’s elements cannot be compared using default comparator. Doing so would result in ClassCastException:

package com.farenda.java;

public class User {

    private final String name;

    public User(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return name;
    }
}

To be able to compare such Users, we need a Comparator that will compare them in a way specified by use. In our case it would be by name:

package com.farenda.java;

import java.util.Comparator;

/**
 * Compares Users using only their names.
 */
public class NameComparator implements Comparator<User> {
    @Override
    public int compare(User u1, User u2) {
        return u1.getName().compareTo(u2.getName());
    }
}

Now, lets assume that we have a list of such users and we would like to quickly find user by name. It could be done in two ways illustrated in the following Java code:

package com.farenda.java;

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

public class CollectionsBinarySeachComparator {

    // we've got 1000s of users to search through ;-)
    private static final List<User> users = Arrays.asList(
            new User("Jon Snow"),
            new User("Cersei"),
            new User("Joffrey"),
            new User("Sansa"),
            new User("Littlefinger"),
            new User("Daenerys")
    );

    public static void main(String[] args) {
        withDefaultComparator();
        withNameComparator();
    }

    private static void withDefaultComparator() {
        System.out.println("Default Comparator");

        // Get names of users:
        // The below Java 8 code is the same as:
        // names = new List; for(User u : users) names.add(u.getName());
        List<String> names = users
                .parallelStream()
                .map(User::getName)
                .collect(Collectors.toList());

        System.out.println("Unsorted names: " + names);

        // Binary search needs sorted data:
        Collections.sort(names, null);
        System.out.println("Names sorted using default comparator: " + names);

        // Search using default Comparator:
        int idx = Collections.binarySearch(names, "Daenerys", null);
        System.out.println("Found 'Daenerys' at index: " + idx);
    }

    private static void withNameComparator() {
        System.out.println("Name Comparator");

        System.out.println("Unsorted users: " + users);

        NameComparator nameComparator = new NameComparator();
        // binary search expects sorted data:
        Collections.sort(users, nameComparator);
        System.out.println("Users sorted using NameComparator: " + users);

        int idx = Collections.binarySearch(
                users, new User("Daenerys"), nameComparator);
        System.out.println("Found 'Daenerys' at index: " + idx);
    }
}

The first way, in method withDefaultComparator, we pass “null” as comparator, which means to use the Default Comparator. In the method we cannot use default comparator directly, because it operates only on mutually comparable elements, so it takes comparable elements (names) from User class and then does sorting and binary search on them.

Remember that sort and binarySearch methods must use the same comparator!

In the other method (withNameComparator) we use our own Java comparator that compares users using their names. In such case we can sort and search a collection directly, without any conversions!

Running the example Java code gives the following result:

Default Comparator
Unsorted names: [Jon Snow, Cersei, Joffrey, Sansa, Littlefinger, Daenerys]
Names sorted using default comparator: [Cersei, Daenerys, Joffrey, Jon Snow, Littlefinger, Sansa]
Found 'Daenerys' at index: 1
Name Comparator
Unsorted users: [Jon Snow, Cersei, Joffrey, Sansa, Littlefinger, Daenerys]
Users sorted using NameComparator: [Cersei, Daenerys, Joffrey, Jon Snow, Littlefinger, Sansa]
Found 'Daenerys' at index: 1

In Game Of Thrones many people die, so the list of all actors is very big. Binary Search may be helpful here. ;-)

Share with the World!
Categories Java Tags algorithms, java-collections
Previous: Java binary search
Next: Java safe List

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 © 2022

sponsored