我有一个关于二进制搜索算法的结果的问题，因为得到了缺失的值。程序希望你输入城市名称，并在读取文件中的每一行并将每个变量分配给城市对象后显示输入城市名称的结果。但是在结果部分有一个问题。
列表中有3个叫 "莫斯科 "的城市名，输入 "莫斯科 "后显示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();
}
}
}
这是我的城市.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
既然你是在没有递归的情况下求解，我想你是想避免递归，那么你需要创建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;
}
虽然这段代码太多，但用递归的方法会更优雅。
你的二进制搜索算法不支持重复 。在
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 对数组进行排序后的方法。