2

我已经编写了一个二进制搜索算法，它可以正常工作，但是当数组中有重复项或数组中的两个或多个数字时它不能正常工作，它返回数组中未找到的值。我能做些什么来解决这个问题，我需要在数组中搜索任何重复项以处理重复项吗？或者我可以阻止随机数生成器生成重复项吗？

这是代码：

public class BinarySearch {

    static int RandomNum;
    static int NumSize;
    static int[] arr;
    static int rangeOfNum;
    static int LookFor;
    static Random numGen = new Random();
    static Scanner Input = new Scanner(System.in);
    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("Enter the size of the data set");
        NumSize = Input.nextInt();
        System.out.println("Enter the range of the random numbers");
        rangeOfNum = Input.nextInt();
        arr = new int[NumSize];
        for (int i = 0; i <= NumSize-1; i++) {
            RandomNum = numGen.nextInt(rangeOfNum);
            arr[i] = RandomNum; 
        }
        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++)
        System.out.println("Number is: " + arr[i]);
        System.out.println("Enter number you want to search for: ");
        LookFor = Input.nextInt();
        binarySearch(arr[0], arr.length-1, LookFor, arr);
    }
    //Binary Search Algorithm
    public static int binarySearch(int LowIndex, int HighIndex, int Target, int[] array) {  
        if (LowIndex <= HighIndex) {
            int MidIndex = (LowIndex + HighIndex)/2;
            if (array[MidIndex] == Target){
                System.out.println("Found target value at index " + MidIndex);
                return Target;}
                else if (array[MidIndex] > Target)
                    return binarySearch(LowIndex, MidIndex-1, Target, array);
                    else 
                        return binarySearch(MidIndex+1, HighIndex, Target, array);
        }
        System.out.println("target value not found");
        return -1;
    }
}

谢谢您的帮助。

4

1 回答 1

2

第一次调用时，binarySearch您将其调用如下：

binarySearch(arr[0], arr.length-1, LookFor, arr);

将其更改为

binarySearch(0, arr.length-1, LookFor, arr);
于 2013-10-25T19:30:08.000 回答