CODEWITHSUNDEEP
javaarrayssortingbinary-searchindexoutofboundsexception
nicky478
nicky478

Reputation: 15

Binary Search w/o Library Methods

I am trying to construct a binarySearch method that goes through a sorted array, and evaluates whether a given element, given as int target, is present. It will do so by evaluating whether the mean value is greater or less than the target value, and will loop through the first or second half of the array accordingly.

I think I have the basic code down, but I am running into some problems:

I imagine it has to do with my for statements in the respective if cases, but I have tried to debug and cannot. Also, I not permitted to use library methods. Hopefully this question is helpful for other beginners like me. I would think it explores some java concepts like syntax, logic, and basic use Thanks for the help.

public class ArrayUtilities
{
public static void main(String[] args) 
{
  int[] arrayBeingSearched = {0, 3, 6, 9, 12, 15, 19, 21, 90};
  int target = 90; 
  System.out.println("linear: " + linearSearch(arrayBeingSearched, target));
  System.out.println("binary: " + binarySearch(arrayBeingSearched, target)); 

}



public static boolean binarySearch(int[] arrayBeingSearched, int target)
 {

  boolean binarySearch = false;
  for (int i = 0; i < arrayBeingSearched.length; i++){
  int left = 0; //array lower bound
  int right = arrayBeingSearched.length - 1; //array upper bound
  int middle = ((right - left) / (2)); //array mean

  if(arrayBeingSearched[middle] == target){
   binarySearch = true;
  }
  else if(arrayBeingSearched[middle] < target){

    for(int j = middle + 1; j < arrayBeingSearched.length - 1; j ++){
      int newLeft = arrayBeingSearched[j ++];
      if(arrayBeingSearched[newLeft] == target){
      binarySearch = true;
      break;
      }
      else{
        binarySearch = false;
      }

    }
  }
  else if(arrayBeingSearched[middle] > target)

    for(int l = 0; l < middle - 1; l ++){
      int newRight = arrayBeingSearched[l ++];
      if(arrayBeingSearched[newRight] == target){
      binarySearch = true;
      break;
      }
      else{
        binarySearch = false;

      }
  }

  else{
    binarySearch = false;
  }
}

return binarySearch;
}

}

Okay, based on the comments, would this be a better representation? The first comment answered my question mostly but I just wanted to follow up:

public static boolean binarySearch(int[] array, int target)    
    {  
        int start = 0;  
        int end = array.length - 1;  

        while (start <= end)   
        {  
            int middle = start + (end - start)/2;  
            if (array[middle] == target) {  
                return true;  
            }  
            else if (array[middle] > target)    
            {  
                end = middle - 1;  
            }  
            else start = middle + 1;  
        }  
        return false;  
    }
}

Upvotes: 0

Views: 603

Answers (3)

Jon Skeet
Jon Skeet

Reputation: 1500495

This is a bad start:

for (int i = 0; i < arrayBeingSearched.length; i++)

That's a linear search, with something else within it. I haven't followed exactly what you're doing, but I think you should probably start again... with a description of binary search in front of you.

Typically a binary search loop looks something like:

int left = 0;                            // Inclusive lower bound
int right = arrayBeingSearch.length;     // Exclusive upper bound
while (left < right) {
    // Either change left, change right, or return success
    // based on what you find
}

Upvotes: 3

ajb
ajb

Reputation: 31689

I'm sure there are other problems (see Jon's answer), but I wanted to mention that code like this:

for(int j = middle + 1; j < arrayBeingSearched.length - 1; j ++){
  int newLeft = arrayBeingSearched[j ++];

will not do what you want. The for statement says that each time the program goes through the loop, it will add 1 to j (at the end of the loop code). But the next statement will use j as an index and then add 1 to it. The result is that each time you go through the loop, 1 will be added to j twice, so you're basically looking only at every other element. If this were otherwise correct (which I don't think it is), I'd say you definitely need to remove the ++ from the second line.

Upvotes: 0

cangrejo
cangrejo

Reputation: 2202

When your middle element is smaller than the target, you do this 

int newLeft = arrayBeingSearched[j ++];
if(arrayBeingSearched[newLeft] == target) //...

And the equivalent when it's larger.

That is, you are taking an element of the array and using it as an index. Your array could contain only one element with a value of 1000, which is why you're running into an ArrayIndexOutOfBoundsException.

Upvotes: 1

Related Questions