Thread: Binary Search Help!

I recommend giving it a try. We are not a code service so no one is going to do this for you, but we will try and help along the way if you post code and explain your problem or question thoroughly.

public class BinarySearch
{
  public static final NOT_FOUND = -1;
  public static int binarySearch (Integer [] a, int x)
   {
      int low=0;
      int high = a.length - 1;
      int mid;
      while (low <= high)
      {
	 mid = (low + high) / 2;
	 if (a[mid] .comareTo (x)<0)
	    low = mid + 1;
	 else if (a[mid] .comareTo (x) > 0)
	    high = mid - 1;
	 else
	    return mid;
      {
	return NOT_FOUND;
   }
 
   public static void main(String[] args)
   {
      int SIZE = 8;
      Integer[] a = new Integer[ SIZE ];
      for (int i=0; i<SIZE; i++)
      a[i] = new Integer(i * 2)
      for (int i=0; i<SIZE*2, i++)
	 System.out.println("Found" + i + " at " +)
binarySearch(a, new Integer (i)));
   }
}

Heres the Binary Search code that I have, do I write a separate code to sort the numbers? I tried, but the decimals causes it to come back with an error:

public class BinarySearchArray {
    public static void main(String[] args) {
        int unsortedArray[] = {10, -3,5, 24, 45.3, 10.5};
        int i;
 
        bubbleSort(unsortedArray, unsortedArray.length); 
 
        System.out.println("After sorting, the list elements are: ");
 
        for(i=0; i<unsortedArray.length; i++) {
            System.out.print(unsortedArray[i] + " ");
        }
    }
 
    private static void bubbleSort(int[] unsortedArray, int length) {
        int temp, counter, index;
 
        for(counter=0; counter<length-1; counter++) { //Loop once for each element in the array.
            for(index=0; index<length-1-counter; index++) { //Once for each element, minus the counter.
                if(unsortedArray[index] > unsortedArray[index+1]) { //Test if need a swap or not.
                    temp = unsortedArray[index]; //These three lines just swap the two elements:
                    unsortedArray[index] = unsortedArray[index+1];
                    unsortedArray[index+1] = temp;
                }
            }
        }
    }
}

A binary search requires some sort of sorted structure. Often this is done by creating a binary search tree, but you can implement a binary search on an array by manipulating the indices.

For an ascending sorted array implementation (note: the sorted part is extremely important, you could implement this algorithm for a descending sorted array with a few changes):
1. Set the left index to 0, set the right index to the last element of the array
2. while left index != right index:
3. Compute the middle index by averaging the left and right.
4. If the number at the middle index is greater than the desired number, set the right index to the middle index
5. else if the number at the middle index is smaller than the desired number, set the left index to the middle index
6. else you've luckily found the number. break out of the while loop (note: this is optional and an unnecessary step)
7. end while loop

All of the indices (left, right, and middle) all hold the index of the desired element (if it exists), just check to see if the number at that index is the number you want.

edit:

The problem you have is because you didn't define the type of NOT_FOUND. simply define it as an int.

The second problem is that you're trying to put non-integer data types into an integer array. Integers must not have any numbers after the decimal. The simple solution is to replace every int[] with double[], which is a floating-point data type array.

public class BinarySearch
{
  public static final int = 45.3;
  public static int binarySearch (Integer [] a, int x)
   {
      int low=0;
      int high = a.length; 45.3;
      int mid;
      while (low <= high)
      {
	 mid = (low + high) / 2;
	 if (a[mid] .comareTo (x)<0)
	    low = mid + 1;
	 else if (a[mid] .comareTo (x) > 0)
	    high = mid - 1;
	 else
	    return mid;
      {
	return int;
   }
 
   public static void main(String[] args);
   {
      int SIZE = 45.3;
      Integer[] a = new Integer[ SIZE ];
      for (int i=0; i<SIZE; i++);
      a[i] = new Integer(i * 2);
      for (int i=0; i<SIZE*2, i++);
	 System.out.println("Found" + i + " at " +);
binarySearch(a, new Integer (i)));
   }
}

So I'm still getting errors, is there STILL something wrong with my code?

Please properly format your code with highlight tags. Could you post the error messages you're getting?

You're not suppose to return int, you just need to define that NOT_FOUND is an integer type. Java is strong-typed so you must explicitly define the type of all variables.

public static final int NOT_FOUND;
//... later on when you want to use NOT_FOUND
return NOT_FOUND;

Originally Posted by Allicat

public class BinarySearch
{
  public static final int = 45.3;
  public static int binarySearch (Integer [] a, int x)
   {
      int low=0;
      int high = a.length; 45.3;
      int mid;
      while (low <= high)
      {
	 mid = (low + high) / 2;
	 if (a[mid] .comareTo (x)<0)
	    low = mid + 1;
	 else if (a[mid] .comareTo (x) > 0)
	    high = mid - 1;
	 else
	    return mid;
      {
	return int;
   }
 
   public static void main(String[] args);
   {
      int SIZE = 45.3;
      Integer[] a = new Integer[ SIZE ];
      for (int i=0; i<SIZE; i++);
      a[i] = new Integer(i * 2);
      for (int i=0; i<SIZE*2, i++);
	 System.out.println("Found" + i + " at " +);
binarySearch(a, new Integer (i)));
   }
}

So I'm still getting errors, is there STILL something wrong with my code?

You forgot to give one of the variables a name .

public static final int = 45.3;

Also, "int" values cannot have decimals. The decimals will just be ignored if you do, if I recall correctly. Use a "double" instead. Like this:

public static final double varname = 45.3;

There is also a random 45.3 that I am confused about.

int high = a.length; 45.3;

The 45.3 shouldn´t be there, since it does nothing and may cause errors depending on how picky the compiler is (have not tested it, lol).

And about these two lines:

int SIZE = 45.3;
Integer[] a = new Integer[ SIZE ];

As said before, an "int" cannot store decimal values. And other then that, an array cannot have a size of 45.3. They can only have non-decimal and non-negative sizes.

I hope this helps a bit .