Java 对字符串数组实现二分查找
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/32260445/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Implementing binary search on an array of Strings
提问by user5274758
I'm having a bit of trouble with this. The input array is based on file input and the size of the array is specified by the first line in the file. The binarySearch method seems to look alright but it doesn't seem to be working would. Anybody be able to help? Thanks.
我在这方面有点麻烦。输入数组基于文件输入，数组的大小由文件中的第一行指定。binarySearch 方法看起来不错，但它似乎不起作用。有人可以帮忙吗？谢谢。
public static int binarySearch(String[] a, String x) {
int low = 0;
int high = a.length - 1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid].compareTo(x) < 0) {
low = mid + 1;
} else if (a[mid].compareTo(x) > 0) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Enter the name of your file (including file extension): ");
String filename = input.next();
String[] numArray;
try (Scanner in = new Scanner(new File(filename))) {
int count = in.nextInt();
numArray = new String[count];
for (int i = 0; in.hasNextInt() && count != -1 && i < count; i++) {
numArray[i] = in.nextLine();
}
for (int i = 0; i < count; i++) //printing all the elements
{
System.out.println(numArray[i]);
}
String searchItem = "The";
System.out.println("The position of the String is:");
binarySearch(numArray, searchItem);
} catch (final FileNotFoundException e) {
System.out.println("That file was not found. Program terminating...");
e.printStackTrace();
}
}
回答by Mike Rylander
I believe that your problem is that you forgot to output the results. Try replacing binarySearch(numArray, searchItem);with System.out.println(binarySearch(numArray, searchItem));
我相信你的问题是你忘记输出结果。尝试替换binarySearch(numArray, searchItem);为 System.out.println(binarySearch(numArray, searchItem));
回答by bombe
There are four issues that I can spot in addition to the already mentioned missing print of the result.
除了已经提到的结果缺失打印之外，我还可以发现四个问题。
1: You have a String[]called numArrayand you are searching for a String, "The"the name numArrayis possibly a bit mis-leading.
1：你有一个String[]被叫numArray，你正在搜索一个String，"The"这个名字numArray可能有点误导。
2: I assume you have some sort of specified input file format where the number of Stringin the file are specified by an integeras the first token in the file. This is ok however, as a condition in the for loop that populates the numArraythere is in.hasNextInt(), and the next token is taken out of the Scannerusing in.nextLine(). You should use complementing check/removal methods such as in.hasNext()with in.next(). Check out the ScannerAPI.
2：我假设您有某种指定的输入文件格式，其中文件中的数字String由 an 指定为文件中integer的第一个标记。然而，这是可以的，因为在 for 循环中填充numArraythere is 的条件in.hasNextInt()，并且下一个标记从Scannerusing 中取出in.nextLine()。您应该使用补充检查/删除方法，例如in.hasNext()with in.next()。查看ScannerAPI。
3: The binarySearch(String[], String)method uses String.compareTo(String). This is determines a lexicographical ordering of this Stringto the parameter String. Trying to compare upper case to lower case may not yield what you expect, as "the".compareTo("The")will not result in 0. You should check out the StringAPIfor options to either force all of your input to one case, maybe while reading the file, or use a different flavor of a compare to method.
3：该binarySearch(String[], String)方法使用String.compareTo(String). 这是确定 thisString到参数的字典顺序String。尝试比较大写与小写可能不会产生您期望的"the".compareTo("The")结果，因为不会导致0. 您应该查看StringAPI以获取选项，以将您的所有输入强制为一个案例，也许是在读取文件时，或者使用不同风格的比较方法。
4: The last thing that I see may be considered a bit of a corner case, however with a sufficiently large Stringarray, and a search string that may reside far in the right side, ie. high index side, of the array you may get an ArrayIndexOutOfBoundsException. This is because (low + high)can result in a negative value, when the result "should" be greater than Integer.MAX_VALUE. Then the result is divided by two and still yields a negative value. This can be solved by bit shifting the result instead of dividing by 2, (low + high) >>> 1. Joshua Bloch has a great articleabout this common flaw in divide and conquer algorithms.
4：我看到的最后一件事可能被认为是一种极端情况，但是具有足够大的String数组，并且搜索字符串可能位于右侧很远的位置，即。数组的高索引侧，您可能会得到一个ArrayIndexOutOfBoundsException. 这是因为(low + high)当结果“应该”大于 时，可能会产生负值Integer.MAX_VALUE。然后结果除以二，仍然产生负值。这可以通过对结果进行位移而不是除以 2 来解决(low + high) >>> 1。Joshua Bloch 有一篇很棒的文章，介绍了分治算法中的这个常见缺陷。
回答by Thusitha Indunil
I have added following example for your further referance.
我添加了以下示例供您进一步参考。
import java.util.Arrays;
public class BinaryStringSearch {
public static void main(String[] args) {
String array[] ={"EWRSFSFSFSB","BB","AA","SDFSFJ","WRTG","FF","ERF","FED","TGH"};
String search = "BB";
Arrays.sort(array);
int searchIndex = binarySearch(array,search);
System.out.println(searchIndex != -1 ? array[searchIndex]+ " - Index is "+searchIndex : "Not found");
}
public static int binarySearch(String[] a, String x) {
int low = 0;
int high = a.length - 1;
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid].compareTo(x) < 0) {
low = mid + 1;
} else if (a[mid].compareTo(x) > 0) {
high = mid - 1;
} else {
return mid;
}
}
return -1;
}
}
回答by Vaibhav
I hope it will help:
我希望它会有所帮助：
public static void main(String ar[]){
String str[] = {"account","angel","apple","application","black"};
String search= "application";
int length = str.length-1;
BinarySearchInString findStrin = new BinarySearchInString();
int i = findStrin.find(str, 0, length, search);
System.out.println(i);
}
public int find(String first[], int start, int end, String searchString){
int mid = start + (end-start)/2;
if(first[mid].compareTo(searchString)==0){
return mid;
}
if(first[mid].compareTo(searchString)> 0){
return find(first, start, mid-1, searchString);
}else if(first[mid].compareTo(searchString)< 0){
return find(first, mid+1, end, searchString);
}
return -1;
}
回答by Laurent Caillette
As spotted by @Mike Rylander you forgot to output the result.
正如@Mike Rylander 发现的那样，您忘记输出结果。
You should use Arrays.binarySearchinstead of your own implementation.
您应该使用Arrays.binarySearch而不是您自己的实现。
(As a general rule, JRE libraries are well-tested, well-documented and fast. I googled "java binary search" and this question is well-ranked. I had a try with @Thusitha Indunil's code, which didn't appear to work. I googled harder and found Arrays.binarySearch, which worked.)
（作为一般规则，JRE 库经过充分测试、记录良好且速度快。我在 google 上搜索了“java binary search”，这个问题排名很好。我尝试了 @Thuithha Indunil 的代码，但似乎没有工作。我用谷歌搜索了一番，发现Arrays.binarySearch，这奏效了。）
