文章目录
一、引言
在Java程序开发中，查找操作是一个非常基础且关键的算法需求。其中，二分查找(Binary Search)因其O(log n)的时间复杂度，在大规模有序数据集的查找中具有显著优势。
二、二分查找的基本原理
二分查找算法的核心思想是通过将有序数组不断平分，逐步缩小查找范围来定位目标元素。这种"分而治之"的策略使得每次查找都可以排除掉一半的搜索空间，从而实现对数级的时间复杂度。需要特别注意的是，二分查找的前提条件是操作的数据集必须是有序的。
public class BinarySearchBasic {
public static void main(String[] args) {
List<Integer> numbers = Arrays.asList(1, 3, 5, 7, 9, 11, 13, 15, 17);
// 基本二分查找实现
int target = 7;
int index = basicBinarySearch(numbers, target);
System.out.println("元素 " + target + " 的位置: " + index);
}
public static int basicBinarySearch(List<Integer> list, int target) {
if (list == null || list.isEmpty()) {
return -1;
}
int left = 0;
int right = list.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 避免整数溢出
int midVal = list.get(mid);
if (midVal == target) {
return mid;
} else if (midVal < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 未找到目标元素
}
}
三、Java Collections工具类中的二分查找
Java Collections框架提供了现成的二分查找实现，通过Collections.binarySearch()方法可以直接进行查找操作。这个方法不仅支持基本数据类型，还支持自定义对象的查找。
public class CollectionsBinarySearch {
static class Student implements Comparable<Student> {
private String name;
private int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Student other) {
return Integer.compare(this.score, other.score);
}
@Override
public String toString() {
return String.format("Student{name='%s', score=%d}", name, score);
}
}
public static void main(String[] args) {
// 对基本类型进行二分查找
List<Integer> numbers = Arrays.asList(2, 4, 6, 8, 10, 12, 14);
int numberIndex = Collections.binarySearch(numbers, 8);
System.out.println("数字8的索引位置: " + numberIndex);
// 对自定义对象进行二分查找
List<Student> students = Arrays.asList(
new Student("张三", 75),
new Student("李四", 82),
new Student("王五", 88),
new Student("赵六", 92)
);
Student targetStudent = new Student("查找目标", 88);
int studentIndex = Collections.binarySearch(students, targetStudent);
System.out.println("分数为88的学生索引位置: " + studentIndex);
}
}
四、自定义比较器的二分查找实现
在实际开发中，我们经常需要按照特定的规则进行查找。Java允许我们通过自定义Comparator来实现这一需求。这种方式特别适合那些没有实现Comparable接口的类，或者需要按照不同于自然顺序的方式进行查找的场景。
public class CustomComparatorSearch {
static class Product {
private String name;
private double price;
private int stock;
public Product(String name, double price, int stock) {
this.name = name;
this.price = price;
this.stock = stock;
}
// getter方法
public String getName() { return name; }
public double getPrice() { return price; }
public int getStock() { return stock; }
@Override
public String toString() {
return String.format("Product{name='%s', price=%.2f, stock=%d}",
name, price, stock);
}
}
public static void main(String[] args) {
List<Product> products = Arrays.asList(
new Product("商品A", 29.99, 100),
new Product("商品B", 49.99, 50),
new Product("商品C", 99.99, 75),
new Product("商品D", 149.99, 25)
);
// 按价格查找
Comparator<Product> priceComparator =
Comparator.comparing(Product::getPrice);
Product targetPrice = new Product("", 99.99, 0);
int priceIndex = Collections.binarySearch(
products, targetPrice, priceComparator);
System.out.println("价格为99.99的商品索引: " + priceIndex);
// 按库存查找
Comparator<Product> stockComparator =
Comparator.comparing(Product::getStock);
Product targetStock = new Product("", 0, 75);
int stockIndex = Collections.binarySearch(
products, targetStock, stockComparator);
System.out.println("库存为75的商品索引: " + stockIndex);
}
}
五、处理特殊情况
在实际应用中，需要考虑多种特殊情况，如处理重复元素、处理未找到的情况、处理边界值等。
下面的代码展示了如何处理这些特殊情况。
public class SpecialCaseHandler {
public static void main(String[] args) {
// 处理重复元素
List<Integer> numbersWithDuplicates =
Arrays.asList(1, 3, 3, 3, 5, 7, 7, 9);
// 查找第一个出现的位置
int firstOccurrence = findFirstOccurrence(numbersWithDuplicates, 3);
System.out.println("3第一次出现的位置: " + firstOccurrence);
// 查找最后一个出现的位置
int lastOccurrence = findLastOccurrence(numbersWithDuplicates, 3);
System.out.println("3最后一次出现的位置: " + lastOccurrence);
}
public static int findFirstOccurrence(List<Integer> list, int target) {
int left = 0;
int right = list.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (list.get(mid) == target) {
result = mid;
right = mid - 1; // 继续向左搜索
} else if (list.get(mid) < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
public static int findLastOccurrence(List<Integer> list, int target) {
int left = 0;
int right = list.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (list.get(mid) == target) {
result = mid;
left = mid + 1; // 继续向右搜索
} else if (list.get(mid) < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
}
六、性能优化与最佳实践
对于频繁查找操作的场景，应当维护数据的有序性，避免重复排序带来的性能开销。如果数据集经常变动，可以考虑使用TreeSet或TreeMap等自平衡的数据结构。在实现自定义比较器时，应确保比较操作的性能开销尽可能小。对于复杂对象的比较，可以缓存比较字段的值，避免重复计算。
public class OptimizedBinarySearch {
static class CachedComparator implements Comparator<String> {
private final Map<String, Integer> cache = new HashMap<>();
private int getComplexValue(String str) {
return cache.computeIfAbsent(str,
k -> k.chars().sum() * k.length()); // 复杂计算
}
@Override
public int compare(String s1, String s2) {
int val1 = getComplexValue(s1);
int val2 = getComplexValue(s2);
return Integer.compare(val1, val2);
}
}
public static void main(String[] args) {
List<String> strings = Arrays.asList(
"apple", "banana", "cherry", "date", "elderberry");
CachedComparator comparator = new CachedComparator();
Collections.sort(strings, comparator); // 先排序
// 执行多次查找
String target = "cherry";
int index = Collections.binarySearch(strings, target, comparator);
System.out.println("查找结果索引: " + index);
}
}
七、总结
二分查找是一种高效的查找算法，它在有序数据集中能实现O(log n)的时间复杂度。Java通过Collections框架提供了内置的二分查找实现，同时也支持通过自定义比较器来满足特定的查找需求。在日常开发中，合理使用二分查找算法不仅能提升程序性能，也能让代码更加简洁优雅。
标签：Java,String,int,54,List,mid,查找,public,left From： https://blog.csdn.net/weixin_55344375/article/details/144174489