Java 中的二分查找代码

简介

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。它通过不断将搜索区间减半，大大减少了查找所需的时间复杂度，从线性时间（O(n)）降低到对数时间（O(log n)）。在 Java 中，实现二分查找代码可以帮助我们快速定位到目标元素，提高程序的执行效率。本文将详细介绍二分查找在 Java 中的基础概念、使用方法、常见实践以及最佳实践。

基础概念

二分查找的核心思想是将一个有序数组分成两部分，每次检查中间元素，然后根据目标值与中间元素的大小关系，决定继续在左半部分还是右半部分查找。如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在左半部分继续查找；如果目标值大于中间元素，则在右半部分继续查找。重复这个过程，直到找到目标元素或者搜索区间为空。

使用方法

递归实现

public class BinarySearchRecursive {
    public static int binarySearch(int[] arr, int target, int left, int right) {
        if (left > right) {
            return -1; // 表示未找到目标元素
        }
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            return binarySearch(arr, target, left, mid - 1);
        } else {
            return binarySearch(arr, target, mid + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int result = binarySearch(arr, target, 0, arr.length - 1);
        if (result != -1) {
            System.out.println("目标元素 " + target + " 在索引 " + result + " 处找到。");
        } else {
            System.out.println("未找到目标元素 " + target);
        }
    }
}

迭代实现

public class BinarySearchIterative {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1; // 表示未找到目标元素
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 7;
        int result = binarySearch(arr, target);
        if (result != -1) {
            System.out.println("目标元素 " + target + " 在索引 " + result + " 处找到。");
        } else {
            System.out.println("未找到目标元素 " + target);
        }
    }
}

常见实践

在整数数组中查找

上述代码示例展示了如何在整数数组中进行二分查找。在实际应用中，我们可能会遇到不同类型的数据和不同的需求。例如，我们可能需要查找第一个或最后一个出现的目标元素。

public class BinarySearchFirstAndLast {
    public static int findFirstOccurrence(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                result = mid;
                right = mid - 1; // 继续在左半部分查找第一个出现的位置
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    public static int findLastOccurrence(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                result = mid;
                left = mid + 1; // 继续在右半部分查找最后一个出现的位置
            } else if (arr[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 3, 3, 5, 7, 9};
        int target = 3;
        int first = findFirstOccurrence(arr, target);
        int last = findLastOccurrence(arr, target);
        if (first != -1 && last != -1) {
            System.out.println("目标元素 " + target + " 第一个出现的位置在索引 " + first + " 处。");
            System.out.println("目标元素 " + target + " 最后一个出现的位置在索引 " + last + " 处。");
        } else {
            System.out.println("未找到目标元素 " + target);
        }
    }
}

在自定义对象数组中查找

如果数组元素是自定义对象，我们需要实现 Comparable 接口或者提供一个 Comparator 来定义对象之间的比较规则。

import java.util.Arrays;
import java.util.Comparator;

class Person implements Comparable<Person> {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Person other) {
        return this.age - other.age;
    }
}

public class BinarySearchCustomObject {
    public static int binarySearch(Person[] arr, Person target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int comparison = arr[mid].compareTo(target);
            if (comparison == 0) {
                return mid;
            } else if (comparison > 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Person[] people = {
            new Person("Alice", 20),
            new Person("Bob", 25),
            new Person("Charlie", 30)
        };
        Person target = new Person("Bob", 25);
        Arrays.sort(people);
        int result = binarySearch(people, target);
        if (result != -1) {
            System.out.println("目标对象在索引 " + result + " 处找到。");
        } else {
            System.out.println("未找到目标对象。");
        }
    }
}

最佳实践

数组预处理

在进行二分查找之前，确保数组是有序的。如果数组无序，需要先进行排序。可以使用 Arrays.sort() 方法对数组进行排序。

边界条件处理

在实现二分查找时，要特别注意边界条件的处理。例如，当数组为空或者目标元素不存在时，要返回合适的结果（通常为 -1）。

性能优化

虽然二分查找本身已经是一种高效的算法，但在某些情况下，我们可以进一步优化性能。例如，避免在每次迭代中重新计算中间索引，可以预先计算并存储。

小结

本文详细介绍了 Java 中二分查找的基础概念、使用方法、常见实践以及最佳实践。通过递归和迭代两种方式实现了基本的二分查找，并展示了如何在整数数组和自定义对象数组中进行查找。同时，强调了在实际应用中需要注意的数组预处理、边界条件处理和性能优化等问题。掌握这些知识和技巧，能够帮助我们更高效地使用二分查找算法，提升程序的性能。

参考资料

《Effective Java》
Oracle Java 官方文档
《算法导论》