0

我正在尝试编写一个程序，该程序将采用排序整数的ArrayList，并且将有一个二进制搜索方法，您可以在其中指定要从ArrayList返回的范围和值。

import java.util.ArrayList;

public class ArraySearch {
    ArrayList<Integer> myArrayList = new ArrayList<Integer>();
    static ArrayList<Integer> range = new ArrayList<Integer>();

public static ArrayList<Integer> binarySearch(ArrayList<Integer> arrayList, int min, int max, int first, int last)
                                        throws NotFoundException {
    if(first > last) {
        throw new NotFoundException("Elements not found.");
    }
    else {
        int middle = (first + last) /2;
        int mid_number = arrayList.get(middle);

        if(mid_number >= min && mid_number <= max)
        {
            range.add(middle);
        }

        if(mid_number <= min) {
            if(mid_number == min) {
                range.add(arrayList.get(middle));
                return binarySearch(arrayList, min, max, first, middle-1);
            }
            return binarySearch(arrayList, min, max, first, middle-1);
        }
        else {
            if(mid_number == max) {
                range.add(arrayList.get(middle));
                return binarySearch(arrayList, min, max, middle+1,last);
            }
            return binarySearch(arrayList, min, max, middle+1,last);
        }
    }   
}

public static void main (String [] args) throws NotFoundException {
    ArrayList<Integer> a = new ArrayList<Integer>();
    a.add(0);       
                a.add(1);
    a.add(2);
    a.add(3);
    a.add(6);
    a.add(7);
    a.add(7);
    a.add(10);
    a.add(10);
    a.add(10);

    binarySearch(a, 3, 7, 0, 9);
}

}

我能得到一些帮助吗？
我不知道应该返回ArrayList范围的基本情况条件。而且我想我可能把二分搜索方法的逻辑弄错了。

4

1 回答 1

0

首先，找到元素的下标范围。然后，找到元素的上索引范围。要找到较低的索引范围，当你找到元素时，而不是像我们在正常搜索中那样跳出循环。将值放入 index 并使中间值比您正在检查的当前索引小一。这将使循环再次找到较低的索引，而不是在第一个索引处停止。同样对于上索引，更新开始到我们正在检查的当前索引 + 1。看看代码。

public ArrayList<Integer> searchRange(ArrayList<Integer> a, int b) {
    int first=lowerIndex(a,b);
    int last=upperIndex(a,b);
    ArrayList<Integer> result= new ArrayList<Integer>();
    result.add(first);
    result.add(last);
    return result;

}

public int upperIndex(ArrayList<Integer> a, int b) {
    int index=-1; //will return -1 if element not found.
    int start=0;
    int end=a.size()-1;

    while(start<=end){
        int mid=(start+end)/2;
        if(a.get(mid)==b){
            index=mid;    //Update Index, which is the upper index here.
            start=mid+1; // This is the main step.
        }
        else if(a.get(mid)>b){
            end=mid-1;
        }
        else{
            start=mid+1;
        }
    }


    return index;
}

public int lowerIndex(ArrayList<Integer> a, int b) {
    int index=-1; // will return -1 if element not found
    int start=0;
    int end=a.size()-1;

    while(start<=end){
        int mid=(start+end)/2;
        if(a.get(mid)==b){
            index=mid;  //Update Index, which is the lower index here.
            end=mid-1; // This is the main step .
        }
        else if(a.get(mid)>b){
            end=mid-1;
        }
        else{
            start=mid+1;
        }
    }

    return index;
}
于 2018-06-26T23:50:51.020 回答