当前位置：首页 > 后端开发 > 正文

java二分查找怎么做

admin
后端开发
2025-07-09
7

va二分查找需先确保数组有序，通过不断将查找范围缩小一半来定位目标值

分查找,也称为折半查找，是一种在有序数组中查找特定元素的高效算法，它通过不断将查找范围减半，从而快速定位目标值，以下是如何在Java中实现二分查找的详细步骤和示例代码。

二分查找的基本步骤

初始化查找范围：定义两个变量low和high，分别表示查找范围的左边界和右边界，初始时，low为0，high为数组长度减1。
计算中间索引：在每次循环中，计算中间索引mid，可以通过(low + high) / 2得出，为了避免整数溢出，推荐使用low + (high low) / 2。
比较中间元素和目标值：
- 如果中间元素等于目标值,则查找成功，返回中间索引。
- 如果中间元素大于目标值,则目标值只可能在左侧的子数组中，更新high为mid 1。
- 如果中间元素小于目标值,则目标值只可能在右侧的子数组中，更新low为mid + 1。
重复以上步骤：直到找到目标值或查找范围为空（即low大于high），如果查找范围为空，则表示目标值不存在于数组中。

Java实现二分查找的代码示例

以下是一个Java实现二分查找的示例代码：

public class BinarySearchExample { public static int binarySearch(int[] array, int target) { int low = 0; int high = array.length 1; while (low <= high) { int mid = low + (high low) / 2; // 防止整数溢出 if (array[mid] == target) { return mid; // 找到目标值，返回索引 } else if (array[mid] < target) { low = mid + 1; // 目标值在右半部分 } else { high = mid 1; // 目标值在左半部分 } } return -1; // 未找到目标值，返回-1 } public static void main(String[] args) { int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15}; int target = 7; int result = binarySearch(sortedArray, target); if (result != -1) { System.out.println("目标值 " + target + " 在数组中的索引为: " + result); } else { System.out.println("目标值 " + target + " 不在数组中"); } } }

代码解释

初始化：low和high分别初始化为数组的起始和结束索引。
循环条件：while (low <= high)确保在查找范围内继续查找。
计算中间索引：int mid = low + (high low) / 2;这样计算可以避免low + high可能导致的整数溢出。
比较和更新：根据中间元素与目标值的比较结果，更新low或high，从而缩小查找范围。
返回结果：如果找到目标值，返回其索引；否则返回-1。

使用Java标准库中的二分查找方法

Java的java.util.Arrays类提供了内置的二分查找方法，使用起来更加简便，以下是使用标准库中的二分查找方法的示例：

import java.util.Arrays; public class StandardLibraryBinarySearch { public static void main(String[] args) { int[] sortedArray = {1, 3, 5, 7, 9, 11, 13, 15}; int target = 7; int result = Arrays.binarySearch(sortedArray, target); if (result >= 0) { System.out.println("目标值 " + target + " 在数组中的索引为: " + result); } else { System.out.println("目标值 " + target + " 不在数组中"); } } }

注意事项

数组必须有序：二分查找的前提是数组必须是有序的，否则无法正常工作，如果数组不是有序的，需要先对数组进行排序，然后才能使用二分查找算法。
处理查找不到的情况：如果目标值不在数组中，二分查找会返回一个负数，这个负数是-(插入点) 1，其中插入点是将目标值插入数组后的第一个大于目标值的元素的索引。
时间复杂度：二分查找的时间复杂度为O(log n)，其中n是数组的长度，这使得二分查找在处理大型有序数组时非常高效。