SitePoint Sponsor

User Tag List

Results 1 to 2 of 2
  1. #1
    SitePoint Enthusiast
    Join Date
    Jan 2010
    Posts
    61
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Java Recursive Binary Search

    Can someone help me fix this? I'm getting an IndexArrayOutofBounds error..

    Code Java:
        private static int recursiveBinarySearch(book[] book, String title) {
            int low = 0, high = book.length - 1, middle = (low + high) / 2;
            String bookTitle = title;
     
            book[] newBook = new book[middle];
     
            if (bookTitle.compareTo(book[middle].getTitle()) == 0) // base case
                return middle;
     
            else { // recursive
                if (bookTitle.compareTo(book[middle].getTitle()) < 0) {
                    for (int i = 0; i < (book.length / 2); i++) {
                        newBook[i] = book[i]; // must be new array = to old array
                    }
                }
                else {
                    for (int i = (book.length / 2); i < book.length; i++)  {
                        newBook[i] = book[i];
                    }
                }
                return (recursiveBinarySearch(newBook, bookTitle));
            }
        }

  2. #2
    Follow Me On Twitter: @djg gold trophysilver trophybronze trophy Dan Grossman's Avatar
    Join Date
    Aug 2000
    Location
    Philadephia, PA
    Posts
    20,580
    Mentioned
    1 Post(s)
    Tagged
    0 Thread(s)
    Say your input array has 10 elements.

    middle = (0 + 9) / 2 = 4 (this isn't the middle...)

    then in your loop near the end you try to assign newBook[5] through newBook[9] but declared it as a 4 element array, so only indices 0-3 are valid

    You have a few logic errors you need to fix

    You're kinda losing the benefit of doing a binary search by doing all this extra work, iterating loops and copying the array repeatedly. Instead you can change the function parameters to include the low and high indices and just change these indices as you make recursive calls. You search within a single array, zero loops, constant memory.


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •