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.
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
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!