在字符串数组上实现二进制搜索
我对此有点麻烦。 输入数组基于文件输入，数组的大小由文件中的第一行指定。 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) { 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(); } } 我已经添加了以下示例供您进一步参考。
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; } }
我相信你的问题是忘了输出结果。 尝试替换binarySearch(numArray, searchItem); with System.out.println(binarySearch(numArray, searchItem));
除了已经提到的结果缺失印刷品之外，我还可以发现四个问题。
1：你有一个名为numArray的String[]并且你正在搜索一个String ， "The"名称numArray可能有点误导。
2：我假设您有某种指定的输入文件格式，其中文件中的String数由integer指定为文件中的第一个标记。 但是，这是正常的，作为填充numArray的for循环中的numArray有in.hasNextInt() ，并使用in.nextLine()从Scanner取出下一个标记。 您应该使用补充检查/删除方法，例如in.hasNext()和in.hasNext() in.next() 。 查看Scanner API 。
3： binarySearch(String[], String)方法使用String.compareTo(String) 。 这确定了此String对参数String的词典排序。 试图比较大写和小写可能不会产生你期望的结果，因为"the".compareTo("The")不会导致0 。 您应该查看String API以获取选项，以强制将所有输入强制转换为一个案例，也可以在读取文件时使用，或者使用不同的方法比较。
4：我看到的最后一件事可能被认为是一个角落的情况，但是有一个足够大的String数组，以及一个可能位于右侧的搜索字符串，即。 在数组的高索引端，您可能会得到一个ArrayIndexOutOfBoundsException 。 这是因为(low + high)可能导致负值，当结果“应该”大于Integer.MAX_VALUE 。 然后将结果除以2并仍然产生负值。 这可以通过比特移位结果而不是除以2， (low + high) >>> 1 。 约书亚布洛赫有一篇关于分而治之算法的常见缺陷的文章 。
我希望它会有所帮助：
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; }
正如@Mike Rylander所发现的那样，你忘了输出结果。
您应该使用Arrays.binarySearch而不是您自己的实现。
（作为一般规则，JRE库经过充分测试，记录良好且速度快。我用谷歌搜索“java二进制搜索”，这个问题排名很高。我尝试使用@Thusitha Indunil的代码，但似乎没有我用Google搜索了Arrays.binarySearch ，找到了Arrays.binarySearch ，它起作用了。）