3.4 二分法
定义
二分查找也称折半查找（Binary Search），是一种在有序数组中查找特定元素的算法。它的工作原理是首先确定数组的中间元素，然后将待查找的元素与中间元素进行比较。如果待查找元素等于中间元素，则查找成功；如果待查找元素小于中间元素，则在数组的前半部分继续进行二分查找；如果待查找元素大于中间元素，则在数组的后半部分继续进行二分查找。重复这个过程，直到找到目标元素或者确定目标元素不在数组中。
使用场景
二分查找法通常用于以下场景：
有序数组的查找：在已经排序好的数组中查找特定元素时，二分查找法能够以较快的速度找到目标元素。
搜索范围逐渐减小的情况：当搜索范围可以逐步缩小到一个较小的范围时，二分查找法非常有效。这种情况下，每次查找可以将搜索范围减半，因此算法的时间复杂度较低。
需要频繁查找的场景：如果需要对相同的有序数据集进行多次查找，二分查找法的优势会更加显著。虽然对数据集进行排序的初始成本较高，但一旦排序完成，后续的查找操作会更加高效。
时间要求严格的应用：在需要快速响应的应用场景中，如实时系统或大规模数据处理，二分查找法可以提供高效的搜索速度，满足实时性要求。
总之，二分查找法适用于对有序数据集进行快速搜索的场景，特别是对大型数据集和需要频繁查找的情况下，它能够提供较高的搜索效率。
时间复杂度
二分查找法的时间复杂度为 O(log n)，其中 n 是数组的元素个数。相比于线性查找等一些其他搜索算法，二分查找法通常更加高效，特别是在大型数据集上。
代码实现
以下是一个简单的 Java 代码示例，实现了二分查找法：
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;
}
// 如果目标值小于中间元素，则在左半部分继续查找
else if (target < arr[mid]) {
right = mid - 1;
}
// 如果目标值大于中间元素，则在右半部分继续查找
else {
left = mid + 1;
}
}
// 如果未找到目标元素，则返回 -1
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int target = 12;
int index = binarySearch(arr, target);
if (index != -1) {
System.out.println("目标元素 " + target + " 在数组中的索引为：" + index);
} else {
System.out.println("目标元素 " + target + " 不在数组中。");
}
}
}
这段代码中，binarySearch 方法接受一个有序数组 arr 和目标元素 target 作为参数，在数组中查找目标元素的索引。如果找到目标元素，则返回其索引；如果未找到，则返回 -1。main 方法演示了如何调用 binarySearch 方法进行查找。
算法变种
二分查找算法有几种常见的变种，它们针对不同的应用场景做了一些优化或扩展：
- 递归实现
除了使用迭代方式实现二分查找外，也可以使用递归的方式实现。递归实现相对简洁，但可能会带来额外的函数调用开销。下面是一个使用递归实现的二分查找算法的 Java 代码示例：
public class RecursiveBinarySearch {
// 递归实现的二分查找函数
public static int binarySearch(int[] arr, int target, int left, int right) {
if (left > right) {
return -1; // 未找到目标元素，返回 -1
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid; // 找到目标元素，返回索引
} else if (target < arr[mid]) {
return binarySearch(arr, target, left, mid - 1); // 在左半部分继续递归查找
} else {
return binarySearch(arr, target, mid + 1, right); // 在右半部分继续递归查找
}
}
public static void main(String[] args) {
int[] arr = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20};
int target = 12;
int index = binarySearch(arr, target, 0, arr.length - 1);
if (index != -1) {
System.out.println("目标元素 " + target + " 在数组中的索引为：" + index);
} else {
System.out.println("目标元素 " + target + " 不在数组中。");
}
}
}
这个代码示例中，binarySearch 方法通过递归实现二分查找。它接受一个有序数组 arr、目标元素 target，以及搜索范围的左右边界 left 和 right。在每次递归中，它计算数组中间元素的索引 mid，然后与目标元素进行比较。如果目标元素等于中间元素，则返回中间元素的索引；如果目标元素小于中间元素，则在左半部分继续递归查找；如果目标元素大于中间元素，则在右半部分继续递归查找。递归的基本情况是当搜索范围的左边界大于右边界时，表示未找到目标元素，返回 -1。
- 查找第一个等于给定值的元素
当有序数组中存在重复元素时，如果需要找到第一个等于给定值的元素，可以稍作修改。在找到等于给定值的元素时，不立即返回，而是继续向数组左边搜索，直到找到第一个等于给定值的元素。下面是 Java 代码示例：
public class FirstOccurrenceBinarySearch {
// 查找第一个等于给定值的元素的索引
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 (target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 6};
int target = 4;
int index = findFirstOccurrence(arr, target);
if (index != -1) {
System.out.println("第一个等于给定值的元素 " + target + " 在数组中的索引为：" + index);
} else {
System.out.println("数组中不存在等于给定值的元素 " + target);
}
}
}
在这个示例中，findFirstOccurrence 方法用于查找数组中第一个等于给定值的元素的索引。它采用了类似于标准二分查找的思想，但在找到等于给定值的元素时，不直接返回，而是继续在左半部分查找第一个等于给定值的元素。通过不断更新 result 变量，最终可以得到第一个等于给定值的元素的索引。
- 查找最后一个等于给定值的元素
与查找第一个等于给定值的元素类似，只是在找到等于给定值的元素时，继续向数组右边搜索，直到找到最后一个等于给定值的元素。下面是 Java 代码示例：
public class LastOccurrenceBinarySearch {
// 查找最后一个等于给定值的元素的索引
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 (target < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3, 4, 4, 4, 5, 6};
int target = 4;
int index = findLastOccurrence(arr, target);
if (index != -1) {
System.out.println("最后一个等于给定值的元素 " + target + " 在数组中的索引为：" + index);
} else {
System.out.println("数组中不存在等于给定值的元素 " + target);
}
}
}
在这个示例中，findLastOccurrence 方法用于查找数组中最后一个等于给定值的元素的索引。它同样采用了二分查找的思想，在找到等于给定值的元素时，不直接返回，而是继续在右半部分查找最后一个等于给定值的元素。通过不断更新 result 变量，最终可以得到最后一个等于给定值的元素的索引。
- 查找第一个大于等于给定值的元素
当有序数组中不存在等于给定值的元素时，查找第一个大于等于给定值的元素。以下是 Java 代码示例：
public class FirstGreaterThanOrEqualBinarySearch {
// 查找第一个大于等于给定值的元素的索引
public static int findFirstGreaterThanOrEqual(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 {
left = mid + 1;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 5, 5, 5, 7, 8, 9};
int target = 6;
int index = findFirstGreaterThanOrEqual(arr, target);
if (index != -1) {
System.out.println("第一个大于等于给定值的元素 " + target + " 在数组中的索引为：" + index);
} else {
System.out.println("数组中不存在大于等于给定值的元素 " + target);
}
}
}
在这个示例中，findFirstGreaterThanOrEqual 方法用于查找数组中第一个大于等于给定值的元素的索引。它同样采用了二分查找的思想，在找到大于等于给定值的元素时，不直接返回，而是继续在左半部分查找第一个大于等于给定值的元素。通过不断更新 result 变量，最终可以得到第一个大于等于给定值的元素的索引。
- 查找最后一个小于等于给定值的元素
当有序数组中不存在等于给定值的元素时，查找最后一个小于等于给定值的元素。以下是 Java 代码示例：
public class LastLessThanOrEqualBinarySearch {
// 查找最后一个小于等于给定值的元素的索引
public static int findLastLessThanOrEqual(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 {
right = mid - 1;
}
}
return result;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 5, 5, 5, 7, 8, 9};
int target = 6;
int index = findLastLessThanOrEqual(arr, target);
if (index != -1) {
System.out.println("最后一个小于等于给定值的元素 " + target + " 在数组中的索引为：" + index);
} else {
System.out.println("数组中不存在小于等于给定值的元素 " + target);
}
}
}
在这个示例中，findLastLessThanOrEqual 方法用于查找数组中最后一个小于等于给定值的元素的索引。它同样采用了二分查找的思想，在找到小于等于给定值的元素时，不直接返回，而是继续在右半部分查找最后一个小于等于给定值的元素。通过不断更新 result 变量，最终可以得到最后一个小于等于给定值的元素的索引。