CODEWITHSUNDEEP
javaalgorithmsearchbinary-search
SigmaO
SigmaO

Reputation: 71

Binary search algorithm fails for values under the midpoint of two values

I made a binary search program which basically searches for the value by using the divide and conquer method. The problem is that it doesn't work for values under the midpoint of the lowest and highest values in the list. For instance, if I put in 33 and 99, it can find all values above 64 but not below it (or 64 itself). The program returns -1 if it can't find the value. Could someone explain why this is a problem? I'm guessing that that I'm using the algorithm wrong. Also, I want it to be recursive.

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
  }

} 
}

Upvotes: 1

Views: 537

Answers (1)

Gregory Basior
Gregory Basior

Reputation: 290

Try changing the size of the array to be:

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

because the size should not be the value of just the high number but the difference between the low and the high. The search algorithm is correct, but you should call it by sending in 0 as the low value and size of the array as the high value, so your call should look like:

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

Upvotes: 2

Related Questions