二分查找--快速地将搜索空间减半
二分查找是一种在有序数组中查找特定元素的高效算法。其基本思想是将目标值与数组中间元素进行比较，如果目标值与中间元素相等，则查找成功；如果目标值小于中间元素，则在数组的左半部分继续查找；如果目标值大于中间元素，则在数组的右半部分继续查找。这个过程会不断重复，直到找到目标值或者搜索范围为空。
递归实现：
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;
}
}
// 如果没有找到目标值，返回-1
return -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;
}
}
// 如果没有找到目标值，返回-1
return -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的值，将查找范围缩小一半。
这种非递归的方法在某些情况下可能更受青睐，因为它避免了递归可能带来的栈溢出问题，尤其是在处理大规模数据时。此外，非递归版本通常在调试时也更容易跟踪。
在实际的工程实践中，二分查找是一种非常高效的算法，它被广泛应用于多种场景中，尤其是在需要快速查找和排序的情况下。以下是一些常见的使用二分查找解决的问题：
查找有序数组中的元素：
- 最直接的应用是在有序数组中查找一个特定的值。
确定一个值在有序数组中的位置：
- 二分查找可以用来确定一个值在有序数组中的插入位置，这在某些排序算法（如归并排序）中很有用。
查找范围内的第一个和最后一个元素：
- 通过二分查找，可以快速找到有序数组中大于或等于某个值的第一个元素（下界）和小于或等于某个值的最后一个元素（上界）。
实现快速排序算法中的划分操作：
- 在快速排序中，二分查找可以用来快速定位基准元素，从而将数组划分为两个子数组。
解决区间查询问题：
- 在处理区间覆盖问题时，二分查找可以用来确定是否有足够的区间覆盖某个特定的点。
实现二叉搜索树的搜索操作：
- 二叉搜索树（BST）的搜索操作本质上是一个二分查找过程，因为树的结构是有序的。
解决某些动态规划问题：
- 在一些动态规划问题中，如寻找数组中第k大的元素，可以通过二分查找来优化搜索过程。
实现某些算法的优化：
- 例如，计算有序数组中两个元素的最小和最大乘积，可以通过二分查找来找到乘积最大化或最小化的点。
解决等值划分问题：
- 确定一个值是否可以将数组划分为两个具有相等和的子数组。
实现某些在线算法：
- 在线算法需要即时处理数据，二分查找可以用来快速做出决策，如在线拍卖算法中的出价决策。
解决查找最接近的值问题：
- 在有序数组中查找与给定值最接近的元素。
实现某些图算法中的搜索：
- 在某些图算法中，如A*搜索算法，二分查找可以用来优化搜索过程。
二分查找之所以在这些场景中有效，是因为它的时间复杂度为O(log n)，这使得它比线性搜索（O(n)）在大规模数据集上更加高效。然而，需要注意的是，二分查找要求数据是有序的，因此在实际应用中，可能需要先对数据进行排序。
原文地址：https://blog.csdn.net/s8305057/article/details/143769569
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！