使用二进制搜索按顺序添加到ArrayList

大家好，希望你能在这里帮助我，

我的问题是我需要能够使用二进制搜索搜索ArrayList，并找到添加对象的正确位置，以便列表保持有序。 我不能使用集合排序，因为这是一个功课。 我已经正确实现了一个布尔方法，该方法告诉列表是否包含您要搜索的项目。 那段代码在这里：

public static boolean search(ArrayList a, int start, int end, int val){ int middle = (start + end)/2; if(start == end){ if(a.get(middle) == val){ return true; } else{ return false; } } else if(val < a.get(middle)){ return search(a, start, middle - 1, val); } else{ return search(a, middle + 1, end, val); } } 

我需要做的是使用此方法来查看列表中是否已存在该数字，如果返回false，那么我需要能够使用另一个二进制搜索来确定列表中数字（val）应该去的位置。 非常感谢任何帮助，谢谢！

贾斯汀

Answer 1

好吧，您可以返回搜索中的最后一个索引，而不是返回true或false。 因此，如果该值不在List中，则返回您访问过的最后一个索引，并查看该值是否小于或大于该索引处的当前值，并相应地添加新值。

Answer 2

您应该返回已经找到的值的位置，而不是返回布尔值。 循环解决方案是可以的，但对于非常大的List，找到结果将是一个问题。 而不是使用重新尝试来尝试实现基于循环的解决方案。 我创建了一个小小的演示，它将帮助您理解它：

 import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class SourceCodeProgram { private List integers = new ArrayList(); public static void main(String argv[]) throws Exception { SourceCodeProgram test = new SourceCodeProgram(); test.addIntegerToSortedListVerbose(10); test.addIntegerToSortedListVerbose(2); test.addIntegerToSortedListVerbose(11); test.addIntegerToSortedListVerbose(-1); test.addIntegerToSortedListVerbose(7); test.addIntegerToSortedListVerbose(9); test.addIntegerToSortedListVerbose(2); test.addIntegerToSortedListVerbose(5); test.addIntegerToSortedListVerbose(1); test.addIntegerToSortedListVerbose(0); } private void addIntegerToSortedListVerbose(Integer value) { int searchResult = binarySearch(integers, value); System.out.println("Value: " + value + ". Position = " + searchResult); integers.add(searchResult, value); System.out.println(Arrays.toString(integers.toArray())); } private int binarySearch(List list, Integer value) { int low = 0; int high = list.size() - 1; while (low <= high) { int mid = (low + high) / 2; Integer midVal = list.get(mid); int cmp = midVal.compareTo(value); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; } return low; } } 

程序打印：

 Value: 10. Position = 0 [10] Value: 2. Position = 0 [2, 10] Value: 11. Position = 2 [2, 10, 11] Value: -1. Position = 0 [-1, 2, 10, 11] Value: 7. Position = 2 [-1, 2, 7, 10, 11] Value: 9. Position = 3 [-1, 2, 7, 9, 10, 11] Value: 2. Position = 1 [-1, 2, 2, 7, 9, 10, 11] Value: 5. Position = 3 [-1, 2, 2, 5, 7, 9, 10, 11] Value: 1. Position = 1 [-1, 1, 2, 2, 5, 7, 9, 10, 11] Value: 0. Position = 1 [-1, 0, 1, 2, 2, 5, 7, 9, 10, 11]