1

我已经编写了一个二进制搜索程序作为项目的一部分。它会编译并运行，但是当它到达程序的一部分时，它应该在数组中搜索目标值（由用户输入），它什么也没做，它只是让我输入一个目标值，但似乎没有搜索或终止。

这是我的代码：

/**
 * 
 */
package ProofOfConcepts;

import java.util.Random;
import java.util.Scanner;

/**
 * @author Kirome
 *
 */

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;
            System.out.println("Number is: " + RandomNum);  
        }
        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) {
        int MidIndex = (LowIndex + HighIndex)/2;    
        while (LowIndex <= HighIndex) {
            if (array[MidIndex] == Target){
                System.out.println("Target is found at: " + array[MidIndex]);
                if (array[MidIndex] < Target){
                    binarySearch(LowIndex, MidIndex-1, Target, array);
                }
                if (array[MidIndex] > Target){
                    binarySearch(MidIndex+1, HighIndex, Target, array);
                } else {
                    System.out.println("Target number is not in the array");
                }
            }
        }
        System.out.println(array);
        return Target;
    }
}

它令人沮丧，因为我知道它为什么不能正常运行一定很简单。在此先感谢，并且 ps 我不是最好的程序员。

4

3 回答 3

3

如果要使用二进制搜索，则需要排序数据。随机分布的数据不能用二分搜索来搜索。

于 2013-10-24T18:21:40.623 回答
0

重写作为答案——

除了确保您的输入已排序之外，递归二进制搜索方法中还应该有返回值，以便该方法可以正确地将结果返回到原始调用。

例如 -

if (array[MidIndex] < Target)
     return binarySearch(LowIndex, MidIndex-1, Target, array);
else if (array[MidIndex] > Target)
     return binarySearch(MidIndex+1, HighIndex, Target, array);
于 2013-10-24T18:30:06.073 回答
0

在我看来，问题在于将 while 循环与递归结合使用。通常，如果您使用递归来实现二进制搜索，则不需要循环。另外，正如其他人所说，请确保您的数组已排序。

我会试试这个：

public static int binarySearch(int LowIndex, int HighIndex, int Target, int[] array) {     
    if (LowIndex <= HighIndex) {
        int MidIndex = (LowIndex + HighIndex)/2; 
        if (array[MidIndex] == Target){
            return Target;
        else if (Target < array[MidIndex])
            return binarySearch(LowIndex, MidIndex-1, Target, array);
        else 
            return binarySearch(MidIndex+1, HighIndex, Target, array);
    }

    return -1; // couldn't find target
}
于 2013-10-24T18:32:39.950 回答