CODEWITHSUNDEEP
javaalgorithmbinary-search
Chris V.
Chris V.

Reputation: 1143

BinarySearch does not find element in list even when it's there : Java

Can anyone point out where I've gone wrong here? I stepped through it with a debugger and it looks like my algorithm should be finding the search key, but its not. (To check, I printed out the 'found at index' and then the contents of the [sorted] list; the element I searched for, 123, was in the list, but returned a 'not found' value of -1.)

public int binarySearch(ArrayList<Integer> list, int key){
    int foundAtIndex  = -1;
    int midPoint = list.size()/2;
    int midPointValue = list.get(midPoint);

    if(list.size() > 1){
        if(midPointValue == key){
            foundAtIndex = midPoint;
        }
        else if(midPointValue > key){
            ArrayList<Integer> newList = new ArrayList<Integer>();
            for(int i = 0; i < midPoint; i++){
                newList.add(list.get(i));
            }
            midPoint = midPoint / 2;
            binarySearch(newList, key);
        }
        else if(midPointValue < key){
            ArrayList<Integer> newList = new ArrayList<Integer>();
            for(int j = midPoint+1; j < list.size(); j++){
                newList.add(list.get(j));
            }
            midPoint = midPoint / 2;
            binarySearch(newList, key);
        }
    }
    else if(list.size() == 1){
        if(list.get(0) == key){
            foundAtIndex = 0;
        }
    }

    //return the index where the key was found, or -1 if not found
    return foundAtIndex;
}

EDIT: Okay, so it finds it now, but my problem is I need to return the index it was found at in the original array. As it is, it narrows it down then returns the index of the element in 'newList'. So it will always return it as being found at an index in terms of 'newList'. In other words, I'm looking to return an actual foundAtIndex (at what position the value is located at in the original array) as opposed to a boolean, "was/wasn't found" value.

Upvotes: 0

Views: 2706

Answers (3)

Assaf
Assaf

Reputation: 1346

Every time you call binarySearch(newList, key); you are losing the return result.

You need to set foundIndex = binarySearch(newList,key).

Also, because you are relying on list.size() for the midpoint - you are going to need to adjust your return result (otherwise it will always be -1 or 0).

Upvotes: 3

Itay Maman
Itay Maman

Reputation: 30723

Here's a solution that returns the index at the original list. The main change: when you make a recursive call to binarySearch you add to its result the offset of newList (compared to list). In midPointValue > key this offset is zero so there's nothing to add. If midPointValue < key then the offset is midPoint.

public int binarySearch(ArrayList<Integer> list, int key){
  int foundAtIndex  = -1;
  int midPoint = list.size()/2;
  int midPointValue = list.get(midPoint);

  if(list.size() > 1){
    if(midPointValue == key){
      foundAtIndex = midPoint;
    }
    else if(midPointValue > key){
      ArrayList<Integer> newList = new ArrayList<Integer>();
      for(int i = 0; i < midPoint; i++){
        newList.add(list.get(i));
      }
      return binarySearch(newList, key);
    }
    else if(midPointValue < key){
      ArrayList<Integer> newList = new ArrayList<Integer>();
      for(int j = midPoint+1; j < list.size(); j++){
        newList.add(list.get(j));
      }
      return midPoint + binarySearch(newList, key);
    }
  }
  else if(list.size() == 1){
    if(list.get(0) == key){
      foundAtIndex = 0;
    }
  }
  //return the index where the key was found, or -1 if not found
  return foundAtIndex;
}

Additional points:

  • No need to set midPoint before making the next recursive call.
  • It's perfectly legal to have multiple returns inside a method. No need to propagate the result all the way down.
  • The point in midPoint and midPointValue is kind of superfluous. Varialbe names that are too long make it harder to understand the code.
  • Finally, there's no need to create a new list and copy elements from the original list to this new list. You can simply tell the method to examine only a certain part of the original list, by adding an auxiliary method.

Here's how I'd write this method:

public int binarySearch(ArrayList<Integer> list, int key) {
  return binarySearch(list, key, 0, list.size());
}

public int binarySearch(ArrayList<Integer> list, int key, int begin, int end) {

  if(end <= begin) 
    return -1; // Range is empty => key wasn't found

  int mid = (begin + end) / 2;
  int midValue = list.get(mid);

  if(midValue == key) 
    return mid;
  else if(midValue < key) 
    return binarySearch(list, begin, mid);
  else
    return binarySearch(list, mid + 1, end);
}

Upvotes: 1

Sven Marnach
Sven Marnach

Reputation: 601599

You don't store the return values of the recursive calls. Substitute the two lines

binarySearch(newList, key);

by

foundAtIndex = binarySearch(newList, key);

and it should work.

Upvotes: 2

Related Questions