如何在函数中的 Substring 中实现二分查找，在 Comparator 中实现两个值？

Question

我在子字符串中实现二进制搜索时遇到问题。在我的城市对象中，有一个定义为字符串的 cityName 变量。我想输入任何子字符串，如 "Sha"，它显示 "Sha" 的结果。除此之外，还有一个权重变量用于对下降的城市名称进行排序。比如权重值大的在最上面，按照降序排列。

我该怎么做？如何将其添加到 comparater 区域？

这是我的城市对象

public class City implements Serializable{
    private Integer cityWeight;
    private String cityName;
}

下面是我的代码片段。

// 不执行二分查找

public static Integer[] searchByCharacters(List<City> list, String sub) {
        List<Integer> result = new ArrayList<>();
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).getCityName().contains(sub))
                result.add(i);
        }
        return result.stream().toArray(Integer[]::new);
}

我想在代码段上方实现二进制搜索，但它不起作用。

public static Integer[] searchBySubStringCharacter(List<City> list, String sub) {
        List<Integer> result = new ArrayList<>();

        Comparator<City> comparator = new Comparator<City>() {
            public int compare(City node1, City node2) {
                boolean node1Contains = node1.getCityName().contains(sub);
                boolean node2Contains = node2.getCityName().contains(sub);
                if (node1Contains && !node2Contains) {
                    return 1;
                } else if (!node1Contains && node2Contains ) {
                    return -1;
                } else {
                    return 0;
                }
            }
        };

        Collections.sort(list, comparator);
        for (int i = 0; i < list.size(); i++) {
            int index = Collections.binarySearch(list, new City(sub), comparator);
            if (index >= 0)
                result.add(i);
        }

        return result.stream().toArray(Integer[]::new);
    }

此代码显示所有城市列表和二进制搜索的结果。如何从结果中提取所有城市列表？

Answer 1

binarySearch 接受要搜索的键以在列表中输入 class 对象，

public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

所以在binarySearch,

中传递City对象

for (int i = 0; i < list.size(); i++) {
     int index = Collections.binarySearch(list, new City(sub), comparator);
     if (index >= 0)
        result.add(i);
}

此外，如果您使用的是 java8+，则可以将 lambda 用于 Comparator、

Comparator<City> comparator = (node1, node2) -> {
     boolean node1Contains = node1.getCityName().contains(sub);
     boolean node2Contains = node2.getCityName().contains(sub);
     if (node1Contains && !node2Contains) {
        return 1;
     } else if (!node1Contains && node2Contains ) {
        return -1;
     } else {
        return 0;
     }
};

更新：在匹配的情况下要根据权重排序，您需要使用 Integer.compare(node2.getCityWeight(), node1.getCityWeight())、

此外，您不能 binarySearch 使用相同的比较器，因为您不知道要搜索的城市的权重。你可以使用流，

public static Integer[] searchBySubStringCharacter(List<City> list, String sub) {
  List<Integer> result = new ArrayList<>();

  Comparator<City> comparator = (node1, node2) -> {
     boolean node1Contains = node1.getCityName().contains(sub);
     boolean node2Contains = node2.getCityName().contains(sub);
     if (node1Contains && !node2Contains) {
        return 1;
     } else if (!node1Contains && node2Contains ) {
        return -1;
     } else {
        return Integer.compare(node2.getCityWeight(), node1.getCityWeight());
     }
  };
  Collections.sort(list, comparator);

  return IntStream.rangeClosed(0, list.size() - 1)
          .filter(i -> list.get(i).getCityName().contains(sub))
          .boxed()
          .toArray(Integer[]::new);
}

Answer 2

您可以添加从字符串创建城市对象并像这样搜索：

  public static Integer[] searchBySubStringCharacter(List<City> list, String sub) {
        List<Integer> result = new ArrayList<>();

        Comparator<City> comparator = new Comparator<City>() {
            public int compare(City node1, City node2) {
                boolean node1Contains = node1.getCityName().contains(sub);
                boolean node2Contains = node2.getCityName().contains(sub);
                if (node1Contains && !node2Contains) {
                    return 1;
                } else if (!node1Contains && node2Contains) {
                    return -1;
                } else {
                    return 0;
                }
            }
        };

        Collections.sort(list, comparator);
        for (int i = 0; i < list.size(); i++) {
            int index = Collections.binarySearch(list, new City(sub), comparator);
            if (index >= 0)
                result.add(i);
        }

        return result.stream().toArray(Integer[]::new);
    }

，或避免每次迭代都创建城市对象并接受城市作为参数

public static Integer[] searchBySubStringCharacter(List<City> list, City sub) {
        List<Integer> result = new ArrayList<>();

        Comparator<City> comparator = new Comparator<City>() {
            public int compare(City node1, City node2) {
                boolean node1Contains = node1.getCityName().contains(sub.getCityName());
                boolean node2Contains = node2.getCityName().contains(sub.getCityName());
                if (node1Contains && !node2Contains) {
                    return 1;
                } else if (!node1Contains && node2Contains) {
                    return -1;
                } else {
                    return 0;
                }
            }
        };

        Collections.sort(list, comparator);
        for (int i = 0; i < list.size(); i++) {
            int index = Collections.binarySearch(list, sub, comparator);
            if (index >= 0)
                result.add(i);
        }

        return result.stream().toArray(Integer[]::new);
    }

如何在函数中的 Substring 中实现二分查找，在 Comparator 中实现两个值？

How can I implement binary search in Substring in function and two values in Comparator?

java

binary-search