当前位置：首页 > news >正文

Java 二分搜索

news 2025/6/18 18:40:04

二分搜索（Binary Search）是一种高效的搜索算法，用于在有序数组中查找特定元素。它的基本思想是通过将搜索区间分成两半，逐步缩小搜索范围，从而快速找到目标元素。

以下是二分搜索的Java实现：

public class BinarySearch {  // 递归实现二分搜索  public static int binarySearchRecursive(int[] array, int target) {  return binarySearchRecursive(array, target, 0, array.length - 1);  }  private static int binarySearchRecursive(int[] array, int target, int left, int right) {  if (left > right) {  return -1; // 未找到目标元素  }  int mid = left + (right - left) / 2; // 防止(left + right) / 2可能导致的溢出  if (array[mid] == target) {  return mid; // 找到目标元素，返回索引  } else if (array[mid] < target) {  return binarySearchRecursive(array, target, mid + 1, right); // 在右半部分继续搜索  } else {  return binarySearchRecursive(array, target, left, mid - 1); // 在左半部分继续搜索  }  }  // 迭代实现二分搜索  public static int binarySearchIterative(int[] array, int target) {  int left = 0;  int right = array.length - 1;  while (left <= right) {  int mid = left + (right - left) / 2;  if (array[mid] == target) {  return mid; // 找到目标元素，返回索引  } else if (array[mid] < target) {  left = mid + 1; // 在右半部分继续搜索  } else {  right = mid - 1; // 在左半部分继续搜索  }  }  return -1; // 未找到目标元素  }  public static void main(String[] args) {  int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};  int target = 7;  int resultRecursive = binarySearchRecursive(array, target);  int resultIterative = binarySearchIterative(array, target);  System.out.println("Recursive search result: " + resultRecursive);  System.out.println("Iterative search result: " + resultIterative);  }  
}

代码解释

递归实现：
- binarySearchRecursive(int[] array, int target) 是对外公开的递归方法，它调用了一个带有额外参数 left 和 right 的私有递归方法。
- 私有递归方法 binarySearchRecursive(int[] array, int target, int left, int right) 实现了实际的二分搜索逻辑。
- 如果 left 大于 right，表示搜索区间为空，返回 -1 表示未找到目标元素。
- 计算中间索引 mid，并比较 array[mid] 与 target。
- 根据比较结果，递归地在左半部分或右半部分继续搜索。
迭代实现：
- binarySearchIterative(int[] array, int target) 方法使用 while 循环实现二分搜索。
- 初始化 left 和 right 指针，分别指向数组的起始和结束位置。
- 在循环中计算中间索引 mid，并比较 array[mid] 与 target。
- 根据比较结果，更新 left 或 right 指针，缩小搜索范围。
- 如果循环结束仍未找到目标元素，返回 -1。