LearnFrenzy
Sign in Take a free test

Generics · Generics Programs · Question 5

Generic binary search with a comparator in Java Solution, output & explanation

  • Program
  • Medium
  • 0 comments
  • Answer explained
  • Moderated community
Question 5 Back to Exercise

Write a generic binarySearch(List<T>, T key, Comparator<? super T>) that returns the index or −(insertion point) − 1, like the JDK; test it with numbers and with products sorted by price.

Solution
Main.java
import java.util.Comparator;
import java.util.List;

record Product(String name, int price) { }

public class Main {
    static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> cmp) {
        int lo = 0, hi = list.size() - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            int c = cmp.compare(list.get(mid), key);
            if (c < 0) lo = mid + 1;
            else if (c > 0) hi = mid - 1;
            else return mid;
        }
        return -(lo + 1);
    }

    public static void main(String[] args) {
        List<Integer> nums = List.of(3, 8, 15, 21, 42, 57);
        System.out.println(binarySearch(nums, 21, Comparator.naturalOrder()) + " " + binarySearch(nums, 10, Comparator.naturalOrder()) + " " + binarySearch(nums, 99, Comparator.naturalOrder()));

        List<Product> byPrice = List.of(new Product("Cable", 199), new Product("Mouse", 699), new Product("Keyboard", 1499), new Product("Monitor", 9999));
        Comparator<Product> priceOrder = Comparator.comparingInt(Product::price);
        System.out.println(binarySearch(byPrice, new Product("?", 1499), priceOrder) + " " + binarySearch(byPrice, new Product("?", 1000), priceOrder));
    }
}

Output Verified by compiling and running

3 -3 -7
2 -3

10 would be inserted at index 2, giving −3; 99 at index 6, giving −7. The same code searches any type with any ordering.

Discussion & Comments 0

Share your method, a shortcut, or ask about a step you didn't follow.

No comments yet. Be the first to share your solution!

Post your comment

Comments appear after a quick review by our team.

Search LearnFrenzy

Esc

Quick links