Java实现二分查找算法详解

"二分查找算法的Java函数实现" 二分法查找算法，也称为折半查找，是一种在有序数组中查找特定元素的有效方法。它通过不断将搜索区间减半来减少查找次数，从而提高效率。以下是二分查找算法的Java函数实现。 首先，我们来看一个基本的二分查找函数，它接受一个已排序的数组`value`，一个查找范围的起始下标`begin`，终止下标`end`，以及要查找的关键字`key`。函数会返回找到的关键字在数组中的下标，如果没找到则返回-1。 ```java public static <T extends Comparable<? super T>> int binarySearch(T[] value, int begin, int end, T key) { count = 0; // 统计比较次数，计算平均比较次数（ASL） while (begin <= end) { // 边界有效 int mid = (begin + end) / 2; // 取中间位置，当前比较元素位置 // System.out.print("["+mid+"]="+value[mid]+"？"); // 显示比较中间结果，可省略 count++; if (key.compareTo(value[mid]) == 0) { // 两对象相等 return mid; // 查找成功 } else if (key.compareTo(value[mid]) < 0) { // key对象较小 end = mid - 1; // 查找范围缩小到前半段 } else { begin = mid + 1; // 查找范围缩小到后半段 } } return -1; // 查找不成功 } ``` 这个函数首先初始化比较次数`count`为0，然后在while循环中，只要`begin`不大于`end`，就表示查找范围仍然有效。计算中间位置`mid`，然后比较`key`与`value[mid]`。如果两者相等，查找成功并返回`mid`。如果`key`小于`value[mid]`，则更新`end`为`mid - 1`，因为目标元素可能在中间位置的左侧；如果`key`大于`value[mid]`，则更新`begin`为`mid + 1`，因为目标元素可能在中间位置的右侧。如果循环结束仍未找到，说明查找不成功，返回-1。 另一个简化版的二分查找函数，它默认在整个数组范围内进行查找，即`begin`为0，`end`为数组长度减1： ```java public static <T extends Comparable<? super T>> int binarySearch(T[] value, T key) { return binarySearch(value, 0, value.length - 1, key); } ``` 这个简化版的函数直接调用了之前定义的完整版二分查找函数，减少了重复代码，并且提供了更方便的接口。 二分查找算法的时间复杂度为O(log n)，空间复杂度为O(1)，是高效查找算法，尤其适用于大数据量的有序数组或列表。然而，它需要数据预先排序，对于未排序的数据，通常需要先进行排序，这会增加额外的时间成本。