跳到主要内容

Java程序实现二分搜索算法

要理解这个示例，你需要了解以下 Java 编程 主题：

示例：Java 程序实现二分查找算法​

import java.util.Scanner;

// Java 中的二分查找

class Main {
  int binarySearch(int array[], int element, int low, int high) {

    // 重复直到 low 和 high 指针相遇
    while (low <= high) {

      // 获取中间元素的索引
      int mid = low + (high - low) / 2;

      // 如果要查找的元素是中间元素
      if (array[mid] == element)
        return mid;

      // 如果元素小于中间元素
      // 只在中间元素的左侧查找
      if (array[mid] < element)
        low = mid + 1;

      // 如果元素大于中间元素
      // 只在中间元素的右侧查找
      else
        high = mid - 1;
    }

    return -1;
  }

  public static void main(String args[]) {

    // 创建 Main 类的对象
    Main obj = new Main();

    // 创建一个排序数组
    int[] array = { 3, 4, 5, 6, 7, 8, 9 };
    int n = array.length;

    // 从用户获取要查找的元素
    Scanner input = new Scanner(System.in);

    System.out.println("输入要查找的元素:");

    // 要查找的元素
    int element = input.nextInt();
    input.close();

    // 调用二分查找方法
    // 传入参数：数组，元素，第一个和最后一个元素的索引
    int result = obj.binarySearch(array, element, 0, n - 1);
    if (result == -1)
      System.out.println("未找到");
    else
      System.out.println("元素在索引 " + result + " 处找到");
  }
}

输出 1

输入要查找的元素:
6
元素在索引 3 处找到

这里，我们使用了 Java Scanner 类 来获取用户的输入。根据用户的输入，我们使用二分查找来检查数组中是否存在该元素。

我们也可以使用递归调用来执行同样的任务。

  int binarySearch(int array[], int element, int low, int high) {

    if (high >= low) {
      int mid = low + (high - low) / 2;

      // 检查中间元素是否是要查找的元素
      if (array[mid] == element)
        return mid;

      // 在中间元素的左侧查找
      if (array[mid] > element)
        return binarySearch(array, element, low, mid - 1);

      // 在中间元素的右侧查找
      return binarySearch(array, element, mid + 1, high);
    }

    return -1;
  }

这里，binarySearch() 方法会一直调用自身，直到找到元素或者 if 条件失败。

如果你想了解更多关于二分查找算法的信息，请访问 二分查找算法。

最后于 更新