如何修复二进制搜索算法的结果（出现缺失结果）

Question

我在获取二进制搜索算法的结果时遇到了缺失值的问题。该程序希望您输入城市名称，并在读取文件中的每一行并将每个变量分配给城市对象后显示输入城市名称的结果。但是结果部分有问题

列表中有 3 个名为 "Moscow" 的城市名称，输入城市名称 "Moscow" 后显示 2 个结果。

我该如何解决这个问题。我还分享了我的代码片段，如下所示。

这是我的城市对象

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

    }
}

这是我的 cities.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

您的二分查找算法不支持重复项。在

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

您不要查看索引 mid 之前的值。由于您的列表中可能有重复项，因此这些值也可能等于您的搜索词。您可以尝试按照Finding multiple entries with binary search找到解决方案。

您可以使用递归解决方案，例如

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

并在数组排序后在 binarySearch 方法中调用 binarySearchHelper(cities, key, arrList, lo, hi);。

Answer 2

既然你是在没有递归的情况下解决它，我想你想避免它，那么你需要创建 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;
}

尽管代码太多，递归解决方案会更优雅。

如何修复二进制搜索算法的结果（出现缺失结果）

How to fix the result of Binary Search Algorithm(appearing missing result)

java

binary-search