Как я могу реализовать бинарный поиск в подстроке в функции и два значения в компараторе?

Question

У меня проблема с реализацией бинарного поиска по подстроке. В моем объекте City есть переменная cityName, как определено String. Я хочу ввести любую подстроку, такую ​​как "Sha", и она показывает результат "Sha". За исключением этого, есть переменная веса для сортировки названий городов по убыванию. Например, большее значение веса находится сверху, а процесс сортировки основан на убывании.

Как я могу это сделать? Как я могу добавить это в область comparater?

Вот мой объект City

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 принимает ключ для поиска, имеющий тип класса объектов в списке,

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

Итак, передайте City объект в binarySearch,

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

Также, если вы используете java8 +, вы можете использовать лямбду для 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 с таким же компаратором, поскольку вы не знаете вес города, который вы ищете. Вы можете использовать Stream,

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);
    }