2

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

我的问题是我需要能够使用二进制搜索来搜索 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）应该去哪里。任何帮助都非常感谢，谢谢！！！

贾斯汀

4

2 回答 2

3

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

于 2013-03-17T23:46:40.020 回答
2

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

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SourceCodeProgram {

    private List<Integer> integers = new ArrayList<Integer>();

    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<Integer> 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]
于 2013-03-18T00:14:10.767 回答