Recursive binary search on ArrayList

Question

I'm trying to do a recursive binary search on an ArrayList but not sure what the issue with my code is. I have a text file with a bunch of integer numbers that look like this:

217 320 550 212 12 17 3560 2999 211

The problem is that when I input a number to search the ArrayList, it always says the element does not exist, but I know it does!

        public static int binarySearch(List<Integer> arr, Integer l, Integer r, Integer x)
        {
            if (r>=l)
            {
                Integer mid = l + (r - l)/2;

                // If the element is present at the middle itself
                if ((arr.size()/2) == x)
                    return mid;

                // If element is smaller than mid, then it can only
                // be present in left subarray
                if ((arr.size()/2) > x)
                    return binarySearch(arr, l, mid-1, x);

                // Else the element can only be present in right
                // subarray
                return binarySearch(arr, mid+1, r, x);
            }
            // We reach here when element is not present in array
            return -1;
        }   
    }

Any help would be greatly appreciated, new programmer here!

If you post code, you should generally add a tag for the language used. It can help others find the question and it also helps with the color formatting of the code. — crashmstr
– crashmstr, Commented Oct 26, 2017 at 13:29

Óscar López · Accepted Answer · 2017-10-26 02:57:32Z

2

The part where you check if the element is present is wrong, don't do this:

arr.size()/2 == x
arr.size()/2 > x

Instead, do this:

arr.get(mid) == x
arr.get(mid) > x

Because you're supposed to access the element at the mid position, not checking if half the list's size equals x.

answered Oct 26, 2017 at 2:57

Óscar López

237k38 gold badges321 silver badges391 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Usagi Miyamoto · Accepted Answer · 2017-10-26 03:05:50Z

0

You calculate mid, and then use arr.size() / 2, instead...

Replace them with arr.get(mid), something like this:

public static int binarySearch(final List<Integer> arr, final int l, final int r, final Integer x)
{
   if (r >= l)
   {
      final int mid = l + (r - l) / 2;

      // If the element is present at the middle itself
      if (x.equals(arr.get(mid)))
         return mid;

      // If element is smaller than mid, then it can only
      // be present in left subarray
      if (arr.get(mid) > x)
         return binarySearch(arr, l, mid - 1, x);

      // Else the element can only be present in right
      // subarray
      return binarySearch(arr, mid + 1, r, x);
   }
   // We reach here when element is not present in array
   return -1;
}

answered Oct 26, 2017 at 3:05

Usagi Miyamoto

6,3471 gold badge21 silver badges37 bronze badges

1 Comment

AmyF Over a year ago

Thank you!! That was really helpful :D

jdevelop · Accepted Answer · 2017-10-26 02:58:15Z

0

Shouldn't you replace arr.size() with arr[mid] or something like that? Looks like you don't compare the value of an item, but rather the array size itself, which is constant and totally irrelevant.

answered Oct 26, 2017 at 2:58

jdevelop

12.4k11 gold badges63 silver badges119 bronze badges

Collectives™ on Stack Overflow

Recursive binary search on ArrayList

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related