二分查找是一种高效的查找算法，其核心在于每次比较都排除一半的查找范围，从而快速定位目标值，但要求数据必须有序。实现方式有两种：1. 循环实现通过 while(left <= right) 不断调整 left 和 right 的值，计算 mid = left + (right – left)/2 防止溢出；2. 递归实现通过自身调用并传入新的 left 和 right 值缩小查找范围。时间复杂度为 o(log n)，常见变体包括查找第一个大于等于或最后一个小于等于目标值的元素，需细致处理边界条件。应用场景涵盖有序数组查找、特定范围查找、数值逼近、游戏决策及数据库索引等。调试时应检查循环条件、手动模拟、使用断言和编写充分单元测试以减少错误。
二分查找，也叫折半查找，是一种高效的查找算法。它的核心在于每次比较都排除掉一半的查找范围，从而快速定位目标值。关键在于数据必须是有序的。
二分查找的Java实现，就是利用循环或者递归，不断缩小搜索范围，直到找到目标值或者确定目标值不存在。
解决方案
立即学习“Java免费学习笔记（深入）”；
二分查找的实现方式有两种：循环和递归。这里分别给出示例代码。
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; // 防止 (left + right) 溢出 if (arr[mid] == target) { return mid; // 找到目标值，返回索引 } else if (arr[mid] < target) { left = mid + 1; // 目标值在右半部分，更新左边界 } else { right = mid - 1; // 目标值在左半部分，更新右边界 } } return -1; // 没有找到目标值，返回 -1 } public static void main(String[] args) { int[] arr = {2, 5, 7, 8, 11, 12}; int target = 13; int index = binarySearch(arr, target); if (index == -1) { System.out.println("Element is not found!"); } else { System.out.println("Element is found at index: " + index); } }}
这段代码的核心是 while (left <= right) 循环。每次循环都计算中间位置 mid，然后根据 arr[mid] 与 target 的大小关系，调整 left 或 right 的值。mid = left + (right - left) / 2; 这种写法可以有效防止 (left + right) 溢出。
2. 递归实现
public class BinarySearchRecursive { public static int binarySearchRecursive(int[] arr, int target, int left, int right) { if (left > right) { return -1; // 没有找到目标值 } int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { return binarySearchRecursive(arr, target, mid + 1, right); // 在右半部分递归查找 } else { return binarySearchRecursive(arr, target, left, mid - 1); // 在左半部分递归查找 } } public static void main(String[] args) { int[] arr = {2, 5, 7, 8, 11, 12}; int target = 13; int index = binarySearchRecursive(arr, target, 0, arr.length - 1); if (index == -1) { System.out.println("Element is not found!"); } else { System.out.println("Element is found at index: " + index); } }}
递归实现的核心在于 binarySearchRecursive 方法的自身调用。每次调用都传入新的 left 和 right 值，缩小查找范围。
二分查找的时间复杂度是 O(log n)，非常高效。但前提是数组必须是有序的。如果数组无序，需要先排序，排序的时间复杂度通常是 O(n log n)。
二分查找有哪些常见的变体？
二分查找的变体主要体现在对边界条件的处理上。比如，查找第一个大于等于目标值的元素、查找最后一个小于等于目标值的元素等等。这些变体都需要对循环条件和边界条件进行细致的调整。
以查找第一个大于等于目标值的元素为例，代码如下：
public static int binarySearchFirstGreaterOrEqual(int[] arr, int target) { int left = 0; int right = arr.length - 1; int index = -1; while (left = target) { index = mid; right = mid - 1; // 继续在左半部分查找 } else { left = mid + 1; // 在右半部分查找 } } return index;}
关键在于 arr[mid] >= target 时，不仅要记录 mid，还要继续在左半部分查找，直到找到第一个大于等于目标值的元素。
二分查找在实际应用中有哪些场景？
二分查找广泛应用于各种需要快速查找的场景，比如：
有序数组查找： 这是最直接的应用。在排序数组中查找特定范围的元素： 可以结合二分查找的变体实现。数值逼近： 比如求一个数的平方根，可以通过二分查找不断逼近。在某些游戏或算法中进行决策： 比如猜数字游戏，或者在一些搜索算法中进行剪枝。
另外，数据库索引的实现也经常用到二分查找的思想。
二分查找的边界条件容易出错，有什么好的调试技巧？
二分查找的边界条件确实容易出错。调试时，可以采用以下技巧：
仔细检查循环条件： 确保循环条件 left <= right 或 left < right 的使用正确。手动模拟： 选取一些典型的测试用例，手动模拟二分查找的过程，观察 left、right 和 mid 的变化。使用断言： 在代码中加入断言，检查 left、right 和 mid 的值是否符合预期。例如，可以断言 left 始终小于等于 right。编写单元测试： 编写充分的单元测试，覆盖各种边界情况，比如空数组、只有一个元素的数组、目标值在数组的开头或结尾等等。
例如，可以添加如下断言：
assert left <= right : "Left should be less than or equal to right";
通过这些调试技巧，可以有效地减少二分查找的错误。
以上就是Java中如何实现二分查找 掌握二分查找的算法实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/162899.html
微信扫一扫 
支付宝扫一扫 
