java - 入门 Java - 创建成功的二分搜索算法

Question

设计一个包含至少 20 个整数的数组的应用程序。它应该调用一个使用顺序搜索算法来定位其中一个值的模块。模块应记录其进行的比较次数，直到找到该值。然后程序应该调用另一个使用二分搜索算法的模块来定位相同的值。它还应该记录其进行的比较次数。在屏幕上显示这些值。

我已经让顺序搜索正常工作，并且它显示找到所需值所需的迭代次数。但是，我的二分搜索模块遇到了问题。每次它搜索一个值时，它总是返回值 1。这是我排除顺序搜索模块的代码。

感谢任何帮助。

//Scanner class
import java.util.Scanner;
public class JavaProgramCh9Ex7_test {

  //global scanner to read input
  static Scanner keyboard = new Scanner(System.in);

  //size of array
  final static int SIZE = 20;

  //main
  public static void main(String[] args) {

    //populate the array
    int [] twentyNumbers = new int [SIZE];
    populateTwentyNumbersArray(twentyNumbers);

    //sort the numbers using bubble sorting:
    bubbleSort(twentyNumbers);
    displayTwentyNumbersSorted(twentyNumbers); 

    //ask the user for a value to search for:
    int desiredValue = getValidInteger("Search for a number", 1, 20);

    //start the binary search algorithm:
    int binSearchComparison = performBinarySearch (twentyNumbers, desiredValue);
    System.out.println(binSearchComparison);

  }

  //Display the 20 integers in the array in ascending-order:
  public static void displayTwentyNumbersSorted (int [] numArray){
    System.out.println("");
    System.out.println("Here are the 20 numbers sorted in ascending-order");
    for (int i = 0; i < numArray.length; i++) {
      if(i < 19){
        System.err.print(numArray[i] + ", ");
      }
      else{
        System.err.print(numArray[i]);
      }
    }
  }

  //Perform the binary search for the user's desired value:
  public static int performBinarySearch (int [] numArray, int userValue){
    int first = 0;
    int middle;
    int last = (numArray.length - 1);
    int iteration = -1;
    boolean found = false;
    for (int i = 0; i < numArray.length; i++) {
      while ((!found) && (first <= last)) {
        middle = ((first + last) / 2);
        if (numArray [middle] == userValue) {
          found = true;
          iteration = (i + 1);
        }
        if(numArray [middle] > userValue) {
          last = (middle - 1);
        }

        if(numArray [middle] < userValue) {
          first = (middle + 1);
        }
      }
    }
    return iteration;
  }

  //Populate the array with 20 random integers:
  public static void populateTwentyNumbersArray (int [] numArray){
    int number = 0;
    for (int i = 0; i < numArray.length; i++) {
      do{  
        number = getRandomNumber(1, 20);
      }while (checkNum(numArray, number));
      numArray[i] = number;
    }
  }

  //Check to make sure the number is unique:
  public static boolean checkNum (int [] numArray, int num) {
    boolean value = false;
    for (int i = 0; i < numArray.length; i++) {
      if (numArray[i] == num) {
        value = true;
      }
    }
    return value;
  }

  //Sort the array in ascending order
  public static void bubbleSort(int [] numArray){
    int temp;
    int maxElement;
    for(maxElement = (SIZE - 1); maxElement > 0; maxElement--){
      for(int i = 0; i <= (maxElement - 1); i++){
        if(numArray[i] > numArray[i + 1]){
          temp = numArray[i];
          numArray[i] = numArray[i + 1];
          numArray[i + 1] = temp;
        }
      }
    }
  }

  //Get a valid Integer from the user to determine the number of seats sold per section:
  public static int getValidInteger(String msg, int low, int high) {
    int newValue = getInteger(msg);

    //Check that the user entered a valid number within the range:
    while (newValue < low || newValue > high) {
      System.err.println("Please enter a number from " + low + " to " + high + ".");
      newValue = getInteger(msg);
    }
    return newValue;
  }

  //Check for a valid Integer input from the user:
  public static int getInteger(String msg) {
    System.out.println(msg);
    while (!keyboard.hasNextInt()) {
      keyboard.nextLine();
      System.err.println("Invalid integer. Please try again.");
    }
    int number = keyboard.nextInt();
    keyboard.nextLine(); //flushes the buffer
    return number;
  } 

  //Get a random number to represent the computer's choice:
  public static int getRandomNumber(int low, int high){
    return (int)(Math.random() * ((high + 1) - low)) + low;
  }

}

Answer 1

在performBinarySearch中，您检查数组的所有值，这最大化了二分搜索的复杂性，尽管循环对搜索没有任何影响。如果数组中存在该值，则搜索函数在i=0时检查该值是否存在，并设置found=true。之后，内部 while 循环不会始终以 found=true 的形式执行。

因此，如果数组中存在该值，则 iterator=(i+1) 始终为 i=0，否则 iterator= -1.

考虑下面的performBinarySearch函数:

public static int performBinarySearch(int[] numArray, int userValue) {
    int first = 0;
    int middle;
    int last = (numArray.length - 1);
    int iteration = 0;
    boolean found = false;
    while ((!found) && (first <= last)) {
        iteration++;
        middle = ((first + last) / 2);
        if (numArray[middle] == userValue) {
            found = true;
            break;
        }
        if (numArray[middle] > userValue) {
            last = (middle - 1);
        }

        if (numArray[middle] < userValue) {
            first = (middle + 1);
        }
    }
    if (found) return iteration;
    else return -1;
}

在这里，我通过简单的修改重用了您的代码。我删除了多余的外循环，并计算了每次 while 循环执行时的迭代次数。如果找到，则创建 found=true 并中断循环(因为我已经找到了预期值)并返回该值。