如何使用二分搜索来查找数组中具有一定权重的第一个元素（不同数组中的另一个元素）？

Question

这里的所有方法都是正确的，但我的问题是我必须在零件数组中找到具有一定权重的零件。所以在我执行 getweight 方法之后，我想我必须调用它。但代码的最后一部分是我遇到的问题。它以行 public Part getPartWithWeight (int Weight){ 开始

class Robot {
             Part[] parts;
                 public Robot () {// assume these are right}
                 }
                 public void addPart(Part p) { // assume these are right}
                 }

             class Part {
             // Class details not shown
                 public double getWeight() {//... }
                 }
                 public int getPartnum() {//...}
                 }
                 public String getMaterial() {//...}     
                 }

             public Part getPartWithWeight (int weight){
             for(int i = 0; i < parts.length; i ++){
                 if (parts[i].weight == weight) {
                     return parts[i];
                 }
                 }

Answer 1

嗯，这是“开箱即用”版本。

第 1 步编写一个比较器。

class PartComparator implements java.util.Comparator<Part> {
    @Override
    public int compare(Part part1, Part part2) {
        return part1.weight - part2.weight;
    }
    public final static PartComparator instance = new PartComparator();
}

如果您在 Part 中声明它，则比较器类应该是静态的（这是我的建议）。

第 2 步 使用比较器

public Part getPartWithWeight (int weight){
    Part pivot = new Part();
    pivot.weight = weight;
    int idx = Arrays.binarySearch(parts, pivot, PartComparator.instance);
    return parts[idx];
}

Answer 2

if (parts[i].weight == weight)

应该说

if (parts[i].getWeight() == weight)

您应该使用 getWeight() 因为这是 Parts 类中定义的方法。
另外，如果您的问题是从机器人类获取零件数组并在零件类中使用它，那么您应该将其作为参数传递。

public Part getPartWithWeight (int weight, Part[] parts){
  for(int i = 0; i < parts.length; i ++){
    if (parts[i].getWeight() == weight) {
      return parts[i];
    }
  }
}

然后，当您调用 getPartWithWeight() 方法时，请确保将数组也放入其中。

编辑：另外，根据 Ray Cheng 的评论，您要查找的权重应该是 int 但您的 getWeight() 方法返回一个 double...所以您的 getWeight() 应该返回一个 in 或者您应该将其类型转换为在进行比较之前先输入一个 int 。请注意，如果将其类型转换为 int，您将失去一些精度。最好修复您的 getWeight() ，以便它返回您需要的双精度值。

Answer 3

要实现二分搜索，您首先需要将数组切成两半，然后决定要开始搜索的一半。然后，您再次将减半的数组切成两半并重复...

除非您想实现自己的数组，但看起来有一个可以调用的内置数组。

http://docs.oracle.com /javase/7/docs/api/index.html?java/util/Arrays.html