如何修复二分搜索算法的结果(出现缺失结果)

huangapple go评论93阅读模式
英文:

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

问题

关于获取二分搜索算法结果中遗漏值的问题,程序要求您输入城市名称,并在读取每行文件并将每个变量分配给 City 对象后显示输入城市名称的结果。但在结果部分存在问题。

列表中有 3 个名为 "Moscow" 的城市名称,在输入城市名称 "Moscow" 后显示 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();
        }
    }
}

以下是我的 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
英文:

I have a problem about getting the result of Binary Search Algorithm as getting missing values. The program wants you to enter city name and shows the results of entering city names aftering reading each line in file and assigning each variable to City Object. But there is a problem in the result part.

There are 3 city names called "Moscow" in the list and it shows 2 results after entering city name "Moscow".

How can I fix the issue. I also shared my code snippets as shown below.

Here is my City object

public class City implements Serializable, Comparable&lt;City&gt;{

	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 &lt; 1) {
			 return getCityWeight()-compareage;
		 }else {
			 return compareage-getCityWeight();
		 }
		 
	}
}

Here is my cities.txt

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

Here is my process of reading part.

try(BufferedReader br = new BufferedReader(new FileReader(fileLocation))) {
			
			line = br.readLine();
			
			while (( line = br.readLine()) != null) {
		        String[] cityIdInformation =  line.split(&quot;	&quot;);
		        String cityId = cityIdInformation[0];
		        
		        String[] cityNameCountryInformation = cityIdInformation[1].split(&quot;, &quot;);
		        
		        String cityName = cityNameCountryInformation[0];
		        String cityCountry = &quot;&quot;;
		        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);
			}
			
			
		}

Here is my Main part.

private static void enterSearchValue() {
		
		Scanner scanner = new Scanner(System.in);
		
		System.out.print(&quot;Enter the word of character which I want to search : &quot;);
		String charWord = scanner.nextLine();
		
		System.out.println(&quot;%cities.txt&quot;);
		System.out.println(&quot;Search &quot; + charWord);
		
		if(charWord.length() &gt; 3) {
			ProcessMethod.binarySearchProcess(cities, charWord);
		}
		
	}

The function shows the results of array's location and adds its location to Arraylist and shows result

public static void binarySearchProcess(ArrayList&lt;City&gt; cities, String charWord) {
		System.out.println(&quot;binarySearchProcess is working &quot;);
		Integer[] indexArray = BinarySearch.binarySearch(cities, charWord);

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

public static void getValuesFromIndexArray(ArrayList&lt;City&gt; cities, Integer[] indexArray) {
		ArrayList&lt;City&gt; resultCities = new ArrayList&lt;&gt;();
		for (Integer index :indexArray) {
			resultCities.add(cities.get(index));
		}
		
		showSearchCityValues(resultCities);
	}
	
	public static void showSearchCityValues(ArrayList&lt;City&gt; cities) {
		System.out.println(&quot;----------------------------------------&quot;);
		for(City city: cities) {
			System.out.println(&quot;City Weight : &quot; + city.getCityWeight() + 
					           &quot; | City Name : &quot; + city.getCityName() +
					           &quot; | City Country : &quot; + city.getCountryName()
					          );
		}
		System.out.println(&quot;----------------------------------------&quot;);
		System.out.println(&quot;The result of Search Size : &quot; + cities.size());
	}

Here is my binary search algorithm.

public static Integer[] binarySearch(List&lt;City&gt; cities, Comparable key) {
        List&lt;Integer&gt; arrList = new ArrayList&lt;Integer&gt;();
        int lo = 0, hi = cities.size() - 1, mid;
        cities.sort((str1, str2) -&gt; str1.getCityName().compareTo(str2.getCityName()));
        
        while (lo &lt;= 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 &lt; 0)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        return arrList.stream().toArray(Integer[]::new);
    }

Here is the outpuut.

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

答案1

得分: 1

因为你在不使用递归的情况下解决它,我猜你想要避免递归,那么你需要创建两个帮助方法来找到较低和较高的索引,并且需要稍微修改你的 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;
}

虽然这是相当多的代码,使用递归的解决方案会更加优雅。

英文:

Since you're solving it without recursion I guess you want to avoid it, then you need to create 2 helper methods to find the lower and upper indexes and change your binarySearch method a little:

public static Integer[] binarySearch(List&lt;City&gt; cities, Comparable key) {
List&lt;Integer&gt; arrList = new ArrayList&lt;Integer&gt;();
int lo = 0, hi = cities.size() - 1, mid;
cities.sort((str1, str2) -&gt; str1.getCityName().compareTo(str2.getCityName()));
while (lo &lt;= 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 &lt;= upperBoundary; i++) {
arrList.add(i);
}
break;
} else if (cmp &lt; 0)
hi = mid - 1;
else
lo = mid + 1;
}
return arrList.stream().toArray(Integer[]::new);
}
public static int lowerIndex(List&lt;City&gt; cities, Comparable key, int lo, int hi) {
int mid;
int lastMatch = hi;
while (lo &lt;= 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 &lt; 0) {
lo = mid + 1;
} else {
break;
}
}
return lastMatch;
}
public static int upperIndex(List&lt;City&gt; cities, Comparable key, int lo, int hi) {
int mid;
int lastMatch = lo;
while (lo &lt;= 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 &lt; 0) {
hi = mid - 1;
} else {
break;
}
}
return lastMatch;
}

Although this is too much code and a recursive solution would be more elegant.

答案2

得分: 0

你的二分搜索算法不支持重复元素。在以下代码中:

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

你没有查看索引 mid 之前的值。因为在列表中可能存在重复项,这些值也可能等于你要搜索的项。你可以尝试按照 https://stackoverflow.com/questions/12144802/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);

英文:

Your binary search algorithm does not support duplicates . In

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

you do not look at values before index mid. As you can have duplicates in your list these values might also equal your search term. You can try to follow https://stackoverflow.com/questions/12144802/finding-multiple-entries-with-binary-search to find a solution.

You could use a recursive solution, e.g.

private static void binarySearchHelper(
List&lt;City&gt; cities,
String key,
List&lt;Integer&gt; arrList,
int lo,
int hi
) {
if (lo &lt;= 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 &lt; 0) {
binarySearchHelper(cities, key, arrList, lo, mid - 1);
} else {
binarySearchHelper(cities, key, arrList, mid + 1, hi);
}
}
}

and call binarySearchHelper(cities, key, arrList, lo, hi); in your binarySearch method after sorting the array.

huangapple
  • 本文由 发表于 2020年5月2日 19:35:14
  • 转载请务必保留本文链接:https://go.coder-hub.com/61558712.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定