Как исправить результат алгоритма двоичного поиска (появляется пропущенный результат)

Question

У меня проблема с получением результата алгоритма бинарного поиска как получения пропущенных значений. Программа хочет, чтобы вы вводили название города, и показывает результаты ввода названий городов после прочтения каждой строки в файле и назначения каждой переменной City Object. Но есть проблема в части результата.

В списке 3 названия городов с названием "Москва", и после ввода названия города "Москва" отображаются 2 результата.

Как я могу исправить проблему. Я также поделился фрагментами своего кода, как показано ниже.

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

public class City implements Serializable, Comparable<City>{

    private Integer cityWeight;
    private String cityName;
    private String countryName;
    ...

    @Override
    public int compareTo(City o) {
        // TODO Auto-generated method stub
         City city = (City) o;
         int compareage=city.getCityWeight();
         if(compareage < 1) {
             return getCityWeight()-compareage;
         }else {
             return compareage-getCityWeight();
         }

    }
}

Вот мой city.txt

93827
      10381222  Moscow, Russia
      23800 Moscow, Idaho, United States
      2026  Moscow, Pennsylvania, United States

Вот мой процесс чтение части.

try(BufferedReader br = new BufferedReader(new FileReader(fileLocation))) {

            line = br.readLine();

            while (( line = br.readLine()) != null) {
                String[] cityIdInformation =  line.split("  ");
                String cityId = cityIdInformation[0];

                String[] cityNameCountryInformation = cityIdInformation[1].split(", ");

                String cityName = cityNameCountryInformation[0];
                String cityCountry = "";
                if(cityNameCountryInformation.length == 2) {
                    cityCountry = cityNameCountryInformation[1];
                }else {
                    cityCountry = cityNameCountryInformation[2];
                }

                cityId = cityId.trim();
                cityName = cityName.trim();
                cityCountry = cityCountry.trim();

                City city = new City();
                city.setCityWeight(Integer.parseInt(cityId));
                city.setCityName(cityName);
                city.setCountryName(cityCountry);

                cities.add(city);
            }


        }

Вот моя основная часть.

private static void enterSearchValue() {

        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter the word of character which I want to search : ");
        String charWord = scanner.nextLine();

        System.out.println("%cities.txt");
        System.out.println("Search " + charWord);

        if(charWord.length() > 3) {
            ProcessMethod.binarySearchProcess(cities, charWord);
        }

    }

Функция показывает результаты расположения массива, добавляет его местоположение в Arraylist и показывает результат

public static void binarySearchProcess(ArrayList<City> cities, String charWord) {
        System.out.println("binarySearchProcess is working ");
        Integer[] indexArray = BinarySearch.binarySearch(cities, charWord);

        for (int i = 0; i < indexArray.length; i++) {
            System.out.print(indexArray[i] + " ");
        }
        System.out.println();
        ShowResult.getValuesFromIndexArray(cities, indexArray);
    }

public static void getValuesFromIndexArray(ArrayList<City> cities, Integer[] indexArray) {
        ArrayList<City> resultCities = new ArrayList<>();
        for (Integer index :indexArray) {
            resultCities.add(cities.get(index));
        }

        showSearchCityValues(resultCities);
    }

    public static void showSearchCityValues(ArrayList<City> cities) {
        System.out.println("----------------------------------------");
        for(City city: cities) {
            System.out.println("City Weight : " + city.getCityWeight() + 
                               " | City Name : " + city.getCityName() +
                               " | City Country : " + city.getCountryName()
                              );
        }
        System.out.println("----------------------------------------");
        System.out.println("The result of Search Size : " + cities.size());
    }

Вот мой алгоритм двоичного поиска.

public static Integer[] binarySearch(List<City> cities, Comparable key) {
        List<Integer> arrList = new ArrayList<Integer>();
        int lo = 0, hi = cities.size() - 1, mid;
        cities.sort((str1, str2) -> str1.getCityName().compareTo(str2.getCityName()));

        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(cities.get(mid).getCityName());
            if (cmp == 0) {
                arrList.add(mid);
                lo = mid + 1;
            } else if (cmp < 0)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        return arrList.stream().toArray(Integer[]::new);
    }

Вот результат.

Enter the word of character which I want to search : Moscow
%cities.txt
Search Moscow
binarySearchProcess is working 
1 2 
----------------------------------------
City Weight : 23800 | City Name : Moscow | City Country : United States
City Weight : 2026 | City Name : Moscow | City Country : United States
----------------------------------------
The result of Search Size : 2

Answer 1

Поскольку вы решаете это без рекурсии, я думаю, вы хотите избежать этого, тогда вам нужно создать 2 вспомогательных метода, чтобы найти нижний и верхний индексы и немного изменить ваш binarySearch метод:

public static Integer[] binarySearch(List<City> cities, Comparable key) {
    List<Integer> arrList = new ArrayList<Integer>();
    int lo = 0, hi = cities.size() - 1, mid;
    cities.sort((str1, str2) -> str1.getCityName().compareTo(str2.getCityName()));

    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        int cmp = key.compareTo(cities.get(mid).getCityName());
        if (cmp == 0) {
            int lowerBoundary = lowerIndex(cities, key, lo, mid);
            int upperBoundary = upperIndex(cities, key, mid, hi);
            for(int i = lowerBoundary; i <= upperBoundary; i++) {
                arrList.add(i);
            }
            break;
        } else if (cmp < 0)
            hi = mid - 1;
        else
            lo = mid + 1;
    }
    return arrList.stream().toArray(Integer[]::new);
}

public static int lowerIndex(List<City> cities, Comparable key, int lo, int hi) {
    int mid;
    int lastMatch = hi;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        int cmp = key.compareTo(cities.get(mid).getCityName());
        if (cmp == 0) {
            lastMatch = mid;
            hi = mid - 1;
        } else if (cmp < 0) {
            lo = mid + 1;
        } else {
            break;
        }
    }

    return lastMatch;
}

public static int upperIndex(List<City> cities, Comparable key, int lo, int hi) {
    int mid;
    int lastMatch = lo;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        int cmp = key.compareTo(cities.get(mid).getCityName());
        if (cmp == 0) {
            lastMatch = mid;
            lo = mid + 1;
        } else if (cmp < 0) {
            hi = mid - 1;
        } else {
            break;
        }
    }

    return lastMatch;
}

Хотя это слишком много кода и рекурсивное решение было бы более элегантным.

Answer 2

Ваш алгоритм двоичного поиска не поддерживает дубликаты. В

int cmp = key.compareTo(cities.get(mid).getCityName());
if (cmp == 0) {
   arrList.add(mid);
   lo = mid + 1;
}

вы не смотрите значения до индекса mid. Поскольку в вашем списке могут быть дубликаты, эти значения могут также совпадать с вашим поисковым термином. Вы можете попытаться выполнить Поиск нескольких записей с помощью двоичного поиска , чтобы найти решение.

Вы можете использовать рекурсивное решение, например,

private static void binarySearchHelper(
      List<City> cities,
      String key,
      List<Integer> arrList,
      int lo,
      int hi
  ) {
    if (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      int cmp = key.compareTo(cities.get(mid).getCityName());
      if (cmp == 0) {
        arrList.add(mid);
        binarySearchHelper(cities, key, arrList, lo + (mid - lo) / 2, mid - 1);
        binarySearchHelper(cities, key, arrList, mid + 1, mid + (hi - mid + 1) / 2);
      } else if (cmp < 0) {
        binarySearchHelper(cities, key, arrList, lo, mid - 1);
      } else {
        binarySearchHelper(cities, key, arrList, mid + 1, hi);
      }
    }
  }

и вызвать binarySearchHelper(cities, key, arrList, lo, hi); в вашем binarySearch методе после сортировки массива.