华为OD机试 - 最佳植树距离 - 二分查找（Java 2023 B卷 100分）

在这里插入图片描述

一、题目描述

按照环保公司要求，小明需要在沙化严重的地区进行植树防沙工作，初步目标是种植一条直线的树带。

由于有些区域目前不适合种植树木，所以只能在一些可以种植的点来种植树木。在树苗有限的情况下，要达到最佳效果，就要尽量散开种植，不同树苗之间的最小间距要尽量大。

给你一个适合种情树木的点坐标和一个树苗的数量，请帮小明选择一个最佳的最小种植间距。

例如，适合种植树木的位置分别为1,3,5,6,7,10,13 树苗数量是3，种植位置在1,7,13，树苗之间的间距都是6，均匀分开，就达到了散开种植的目的，最佳的最小种植间距是6。

二、输入描述

第1行表示适合种树的坐标数量。

第2行是适合种树的坐标位置。

第3行是树苗的数量。

三、输出描述

最佳的最小种植间距。

四、备注说明

位置范围为1~10000000

种植树苗的数量范围2~10000000

用例确保种植的树苗不会超过有效种植坐标数量

五、二分查找

二分查找（Binary Search），也称为折半查找，是一种在有序数组中查找特定元素的搜索算法。

二分查找的基本思想是将数组分成两部分，确定待查找元素可能存在的那一部分，然后继续对该部分进行二分，直到找到目标元素或者确定该元素不存在于数组中。

比如下面这段Java代码：

public class BinarySearch {  public static int binarySearch(int[] array, int target) {  int left = 0;  int right = array.length - 1;  while (left <= right) {  int mid = (left + right) / 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, 3, 5, 7, 9};  int target = 5;  int result = binarySearch(array, target);  if (result == -1) {  System.out.println("Element not found");  } else {  System.out.println("Element found at index " + result);  }  }  
}

在这个示例中，binarySearch方法接收一个有序数组array和要查找的目标元素target。然后，使用循环进行二分查找，将搜索范围不断缩小，直到找到目标元素或确定该元素不存在于数组中。如果找到目标元素，返回其索引，否则返回-1。

在main方法中，我们定义一个数组和一个目标元素，然后调用binarySearch方法并打印结果。

六、解题思路

第一行输入种树的坐标数量；
第二行输入树的坐标位置，通过java8 Stream表达式（简洁/方便/上档次）快速拆解输入行；
对树的坐标位置进行排序；
第三行输入树苗的数量；
通过二分查找进行比较；
取中间位置mid；
定义变量count，记录植树的总棵数；
取第一棵树的位置；
遍历树的坐标位置arr，并记录相对位置；
输出最佳的最小种植间距。

七、Java算法源码

// 树的坐标位置
public static int[] arr;
// 树苗的数量
public static int num;public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 种树的坐标数量int n = Integer.valueOf(sc.nextLine());// 树的坐标位置arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();// 树苗的数量num = Integer.valueOf(sc.nextLine());// 树的坐标位置排序Arrays.sort(arr);int min = arr[0];int max = arr[n - 1] - arr[0];// 通过二分查找进行比较while (min < max) {// 取中间位置int mid = (min + max) / 2;if (compare(mid)) {min = mid;} else {max = mid - 1;}}System.out.println(max);
}public static boolean compare(int mid) {// 植树的总棵数int count = 1;// 第一棵树的位置int curPos = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] - curPos >= mid) {// 相距位置大于等于 mid，则可以种树count++;// 相对位置需要改变curPos = arr[i];}}return count >= num;
}