二分查找--快速地将搜索空间减半

二分查找是一种在有序数组中查找特定元素的高效算法。其基本思想是将目标值与数组中间元素进行比较，如果目标值与中间元素相等，则查找成功；如果目标值小于中间元素，则在数组的左半部分继续查找；如果目标值大于中间元素，则在数组的右半部分继续查找。这个过程会不断重复，直到找到目标值或者搜索范围为空。

递归实现：

public class BinarySearch {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; // 找到目标值，返回索引}// 如果目标值小于中间元素，则在左半部分继续查找if (target < arr[mid]) {right = mid - 1;} else {// 如果目标值大于中间元素，则在右半部分继续查找left = mid + 1;}}// 如果没有找到目标值，返回-1return -1;}public static void main(String[] args) {int[] arr = {-3, 10, 11, 21, 34, 54, 60, 78};int target = 21;int result = binarySearch(arr, target);if (result != -1) {System.out.println("元素位于数组的索引：" + result);} else {System.out.println("数组中没有找到元素。");}}
}

在这个例子中，binarySearch方法接受一个整型数组arr和一个要查找的target值。如果找到了target值，方法将返回它在数组中的索引；如果没有找到，则返回-1。

请注意，二分查找算法要求数组是有序的。如果数组是无序的，那么在执行二分查找之前需要先对数组进行排序。

非递归实现：

public class BinarySearch {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; // 找到目标值，返回索引}// 如果目标值小于中间元素，则在左半部分继续查找if (target < arr[mid]) {right = mid - 1;} else {// 如果目标值大于中间元素，则在右半部分继续查找left = mid + 1;}}// 如果没有找到目标值，返回-1return -1;}public static void main(String[] args) {int[] arr = {-3, 10, 11, 21, 34, 54, 60, 78};int target = 21;int result = binarySearch(arr, target);if (result != -1) {System.out.println("元素位于数组的索引：" + result);} else {System.out.println("数组中没有找到元素。");}}
}

这段代码与我之前提供的递归版本在逻辑上是相同的，但是它使用了一个while循环来代替递归调用。循环会一直执行，直到left大于right，这意味着查找范围已经为空，无法再继续查找。在每次迭代中，算法都会更新left和right的值，将查找范围缩小一半。

这种非递归的方法在某些情况下可能更受青睐，因为它避免了递归可能带来的栈溢出问题，尤其是在处理大规模数据时。此外，非递归版本通常在调试时也更容易跟踪。

在实际的工程实践中，二分查找是一种非常高效的算法，它被广泛应用于多种场景中，尤其是在需要快速查找和排序的情况下。以下是一些常见的使用二分查找解决的问题：

查找有序数组中的元素：