一、二分查找初体验
大家平时找东西的时候，要是碰到一堆杂乱无章的东西，找起来可就费劲了。但要是东西是排好顺序的，咱就可以用一些聪明的办法，更快地找到想要的东西。在计算机里，面对排好序的数组，二分查找就是这么个聪明的办法。
二分查找的基本思路就是，每次都把查找范围砍一半。想象一下，你现在要在一本字典里找一个单词，你肯定不会一页一页地翻，而是先翻到中间，看看这个位置的单词比你要找的大还是小。要是大了，那你要找的就在前半部分；要是小了，就在后半部分。然后在新的范围里再重复这个过程，直到找到为止。
下面是一个用 Java 实现的简单二分查找示例：
// Java 技术栈
public class BinarySearchExample {
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) {
left = mid + 1; // 目标在右半部分，更新左边界
} else {
right = 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);
}
}
}
在这个示例里，我们定义了一个 binarySearch 方法，它接收一个整数数组和一个目标值作为参数。通过不断地调整左右边界，最终找到目标元素的位置或者确定目标元素不存在。
二、左闭右开与左闭右闭区间的概念
在二分查找中，我们经常会遇到两种区间表示方法：左闭右开区间和左闭右闭区间。这俩概念听起来有点绕，其实很好理解。
左闭右闭区间，就像数学里的 [a, b] 一样，表示这个区间包含了 a 和 b 这两个端点。比如说，数组的索引从 0 到 4，用左闭右闭区间表示就是 [0, 4]，这里面包含了索引 0、1、2、3、4 对应的元素。
左闭右开区间呢，就像 [a, b)，它包含了左端点 a，但不包含右端点 b。还是拿刚才那个数组举例，用左闭右开区间表示就是 [0, 5)，这里面同样包含了索引 0、1、2、3、4 对应的元素。
这两种区间表示方法在二分查找里都很常用，但是使用的时候得注意它们的边界条件，不然很容易出错。
三、左闭右闭区间的二分查找
我们先来看左闭右闭区间的二分查找。在这种情况下，左右边界都包含在查找范围内。下面是 Java 实现的示例：
// Java 技术栈
public class BinarySearchClosedClosed {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1; // 左闭右闭区间，right 初始为数组最后一个元素的索引
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右半部分，更新左边界
} else {
right = mid - 1; // 目标在左半部分，更新右边界
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {2, 4, 6, 8, 10};
int target = 8;
int result = binarySearch(arr, target);
if (result != -1) {
System.out.println("目标元素 " + target + " 的索引是: " + result);
} else {
System.out.println("未找到目标元素 " + target);
}
}
}
在这个示例中，right 初始值是 arr.length - 1，因为我们采用的是左闭右闭区间，right 对应的元素也要参与查找。在 while 循环里，条件是 left <= right，因为当 left 和 right 相等的时候，这个元素也是要检查的。如果中间元素比目标元素小，我们就把 left 更新为 mid + 1；如果大，就把 right 更新为 mid - 1。
四、左闭右开区间的二分查找
接下来看看左闭右开区间的二分查找。这种情况下，左边界包含在查找范围内，右边界不包含。下面是 Java 实现的示例：
// Java 技术栈
public class BinarySearchClosedOpen {
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length; // 左闭右开区间，right 初始为数组长度
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // 目标在右半部分，更新左边界
} else {
right = mid; // 目标在左半部分，更新右边界
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {3, 5, 7, 9, 11};
int target = 9;
int result = binarySearch(arr, target);
if (result != -1) {
System.out.println("目标元素 " + target + " 的索引是: " + result);
} else {
System.out.println("未找到目标元素 " + target);
}
}
}
在这个示例中，right 初始值是 arr.length，因为右边界不包含在查找范围内。while 循环的条件是 left < right，因为当 left 等于 right 的时候，查找范围为空。如果中间元素比目标元素小，left 更新为 mid + 1；如果大，right 更新为 mid，因为 mid 对应的元素不符合要求，而新的右边界也不包含 mid。
五、边界条件陷阱及处理方法
在使用二分查找的时候，边界条件很容易出错。下面给大家列举一些常见的陷阱和对应的处理方法。
1. 死循环问题
在左闭右开区间的二分查找中，如果 right 更新不正确，就可能会陷入死循环。比如，当 right 更新为 mid - 1 而不是 mid 的时候，本来不包含在查找范围的元素可能又被包含进来了，导致陷入循环无法跳出。
2. 索引越界问题
在计算中间位置 mid 的时候，如果使用 (left + right) / 2 ，当 left 和 right 都很大时，可能会导致整数溢出。我们可以使用 left + (right - left) / 2 来避免这个问题。
3. 边界更新错误
在更新左右边界的时候，要根据区间的类型正确更新。左闭右闭区间更新 right 时要减 1，而左闭右开区间更新 right 时直接赋值为 mid。
六、应用场景
二分查找的应用场景非常广泛，只要是有序的数据，都可以考虑使用二分查找来提高查找效率。
1. 数据库查询
在数据库中，索引通常是有序的。当我们进行范围查询或者精确查询时，可以使用二分查找来快速定位数据。
2. 搜索引擎
搜索引擎在处理有序的索引数据时，也会用到二分查找。比如，在搜索关键词时，通过二分查找可以快速找到包含该关键词的文档。
3. 游戏开发
在游戏开发中，有时候需要在有序的关卡列表中查找某个关卡，这时候二分查找就可以派上用场。
七、技术优缺点
优点
- 效率高：二分查找的时间复杂度是 $O(log n)$，相比于线性查找的 $O(n)$，在数据量较大时，效率提升非常明显。
- 代码简单：二分查找的代码实现相对简单，只要理解了基本思路，很容易编写。
缺点
- 数据必须有序：二分查找要求数据必须是有序的，如果数据无序，需要先进行排序，而排序的时间复杂度可能会比较高。
- 适用范围有限：二分查找只适用于静态数据，如果数据经常插入或删除，维护有序性的成本比较高。
八、注意事项
- 区间类型要明确：在使用二分查找时，一定要明确使用的是左闭右闭区间还是左闭右开区间，并且在代码中正确处理边界条件。
- 避免整数溢出：计算中间位置时，要使用
left + (right - left) / 2来避免整数溢出。 - 边界更新要正确：根据区间类型正确更新左右边界，避免出现死循环或索引越界问题。
九、文章总结
二分查找是一种非常实用的查找算法，它通过不断缩小查找范围，提高了查找效率。在使用二分查找时，我们会遇到左闭右开和左闭右闭两种区间表示方法，这两种方法在边界条件的处理上有所不同。我们要明确区间类型，正确处理边界条件，避免陷入死循环、索引越界等陷阱。同时，我们也要了解二分查找的应用场景、优缺点和注意事项，这样才能在实际开发中更好地运用它。
评论