java - 对于两个值的中点以下的值，二进制搜索算法失败

Question

我制作了一个二进制搜索程序，它基本上使用分而治之的方法搜索值。问题是它不适用于列表中最低值和最高值的中点以下的值。例如，如果我输入 33 和 99，它可以找到所有高于 64 但不低于它(或 64 本身)的值。如果找不到该值，程序将返回 -1。有人可以解释为什么这是一个问题吗？我猜我使用的算法错误。另外，我希望它是递归的。

public class BinarySearch
{
 static Console c;
 public static void main (String[] args)
 {
 c = new Console (30,100);
 c.print("Lowest number on the list: ");
 int low = c.readInt();

 int tempLow = low;

 c.print("Highest number on the list: ");
 int high = c.readInt();

 c.print("The number you want to find in the list: ");
 int val = c.readInt();

 int[] nums = new int[high+1];

 c.print("\n");

 for(int i = 1; i < nums.length; i++) //add all the values into the array
 {
  nums[i] = low;
  low++;
 }

 for(int i = 1; i < nums.length; i++) //print hte array
 {
   c.print("[#" + i + "]" + nums[i] + " ");
 }

 c.println("\n\n" + "The position of " + val + " is " + binarySearch(nums, tempLow, high, val));

}

public static int binarySearch(int[] array, int lowestNumber, int highestNumber, int value) 
{

int midpoint = (lowestNumber + highestNumber) / 2; //(x2+x1)/2 finding midpoint in array

if (lowestNumber > highestNumber) 
{
  return -1;
}  

  if (value == array[midpoint]) //if the value we're looking for is the midpoint then return that position of the value in the array
  {
     return midpoint;
  }
  else if (value < array[midpoint]) // otherwise it isn't the value, so if the value is less than the midpoint then search the top half of the array
  {
     return binarySearch(array, lowestNumber, midpoint - 1, value); //send in the lowest number and the midpoint-1 as the highest number (not including midpoint because we already know it isn't the value)
  }
  else   // otherwise it isn't the value, so if the value is less than the midpoint then search the bottom half of the array
  {
     return binarySearch(array, midpoint + 1, highestNumber, value); //send in the highest number and midpoint-1 as the lowest number to find the midpoint between those two
  }

} 
}

Answer 1

尝试将数组的大小更改为:

 int[] nums = new int[high-low+2];

因为大小不应该只是高数的值，而是低和高之间的差值。搜索算法是正确的，但您应该通过发送 0 作为低值和数组大小作为高值来调用它，因此您的调用应该如下所示:

 c.println("\n\n" + "The position of " + val + " is " + binarySearch(nums, 0, nums.length, val));