0

So I'm trying to complete an exercise where I've been asked to implement a method that does a binary search in an ArrayList of objects. From the exercise:

Binary search

In the Main-class, implement a method public static int binarySearch(ArrayList<Book> books, int searchedId), which searches the list it received as a parameter, for a book with an id variable that matches the value of searchedId variable it received as a parameter. If that book is found the method, should return the index it's located at, in the list it received as a parameter. If the book isn't found, the method should return the value -1.

The method must be implemented as a binary search, which assumes the list is ordered. You should also assume, that the ids towards the beginning of the list, are always smaller than the ids towards the end of the list.

I have created two methods, one to check whether the arraylist is sorted (isItSorted) and the other one that will perform the binary search if the aforementioned method evaluates to true (binarySearch). Please see below:

public static boolean isItSorted(ArrayList<Book> books) {
        ArrayList<String> boo = new ArrayList<>();
        String isItSorted = "";
        for (int i = 0; i < books.size(); i++) {
            for (int j = i + 1; j < books.size(); j++) {
                if (books.get(i).getId() < books.get(j).getId()) {
                    isItSorted = "true";
                    boo.add(isItSorted);
                } else {
                    isItSorted = "false";
                    boo.add(isItSorted);
                }
            }
        }
        if (!(boo.contains("false"))) {
            return true;
        }
        return false;
    }

    public static int binarySearch(ArrayList<Book> books, long searchedId) {
        if (searchedId < 0 || books.isEmpty()) {
            return -1;
        } else if (isItSorted(books)) {
            int start = 0;
            int end = books.size() - 1;
            int middle = (start + end) / 2;

            if (books.get(middle).getId() == searchedId) {
                return middle;
            } else if (books.get(middle).getId() > searchedId) {
                end = middle - 1;
            } else if (books.get(middle).getId() < searchedId) {
                start = middle + 1;
            }
            
            while (start <= end) {
                if (books.get(start).getId() == searchedId) {
                    return start;
                }
                start++;
            }
        }
        return -1;
    }

Inside these java files, there's a test package that tests whether my solution is correct or not. While 95% of the tests are successful, when it reaches the method below (where it compares the time of execution compared to my other method (linear search)), I get the error Java outOfMemory heap Space. I use NetBeans. I've already tried the JVM commands. My solution seems to work with every number of objects I've tried, so perhaps there's something wrong with the test code below?

@Test
    @Points("07-05.2")
    public void binarySearchIsFasterThanLinearSearch() throws Throwable {
        ArrayList<Book> books = generateBooks(10000);
        Collections.sort(books, (k1, k2) -> k1.getId() - k2.getId());

        int searched = 1000001;
        long bSearchStart = System.nanoTime();
        int binarySearchId = Searching.binarySearch(books, searched);
        long bSearchEnd = System.nanoTime();
        assertTrue("When binary search does not find what was searched for, it must return -1", binarySearchId == -1);
        long lSearchStart = System.nanoTime();
        int linearSearchId = Searching.linearSearch(books, searched);
        long lSearchEnd = System.nanoTime();
        assertTrue("When linear search does not find what was searched for, it must return -1", linearSearchId == -1);

        long bSearchTime = bSearchEnd - bSearchStart;
        long lSearchTime = lSearchEnd - lSearchStart;

        assertTrue("When there are 10000 books to search, and the searched book is not found, binary search should be a lot faster than linear search. Current this isn't so", bSearchTime * 2 < lSearchTime);
    }
Improve this question
8
  • 1
    Please don't use String for isItSorted. Use a boolean. Much more efficient and much cleaner code. Commented Jun 25, 2020 at 22:36
  • I also suspect that your isItSorted() could be much more efficient. In fact, as it stands right now your call to isItSorted(books) is the slowest part of your implementation. Your "binarySearch" is most definitely not faster than linear search.. as implemente here. Commented Jun 25, 2020 at 22:39
  • @AminM Thank you for the suggestion. I'll change it to boolean Commented Jun 25, 2020 at 22:41
  • the simplest way to do binary search is: 1. look in the middle, is that the item you're looking for? 2. If not, then decide if you want to search on the left or on the right 3. call binarySearch recursively There are of course more efficient ways as well Commented Jun 25, 2020 at 22:41
  • 1
    your binary search doesn't look properly implemented. Start over from scratch with the instructions I gave you. Recursive is easier. Commented Jun 25, 2020 at 22:50

1 Answer 1

Reset to default
1 
        ArrayList<String> boo = new ArrayList<>();
        String isItSorted = "";
        for (int i = 0; i < books.size(); i++) {
            for (int j = i + 1; j < books.size(); j++) {
                if (books.get(i).getId() < books.get(j).getId()) {
                    isItSorted = "true";
                    boo.add(isItSorted);
                } else {
                    isItSorted = "false";
                    boo.add(isItSorted);
                }
            }
        }

Adds on the order of 100 million items to the ArrayList boo.

If you want to check if something is sorted you can use much simpler code:

Book prev = books[0];
for (int i = 1; i < books.size(); i++) {
   if (prev.getId() > books[i].getId()) 
      return false;
}
return true;

But you shouldn't need to call it inside binarySearch() because that will defeat the purpose of binarySearch() and make it as slow as linearSearch().

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

5 Comments

I get it. I got rid of that for loop. But here's the thing. With your isItSorted method, I can't really see if the ids are actually sorted because what if the first (books.get(0)) is less than the last id in the array but between these two, the rest of the numbers are not ordered? What I mean: books.add(new Book(1, "book 1")); books.add(new Book(2, "book 2")); books.add(new Book(4, "book 4")); books.add(new Book(3, "book 3")); books.add(new Book(7, "book 7")) I wanted to see if the whole list of ids is ordered. Any suggestions? Thanks!!
"ordered" means that for each x in the list, x <= x+1. My code finds a violation of that order. Order doesn't mean that there aren't gaps. 1,2,3,4 is in order, but so is 1,1,1,1, and 1,10,20,21,21,22,50
You're right, I understand now. Thanks! It still fails though because binarySearch is slower, since as you said I'm checking if the arrayList is sorted inside the method. How could I make it faster? I can't use the recursive approach, only the iterative.
I removed the isItSorted method and the test passed. Thank you very much again!
iterative is similar to recursive. In this case there's not much to it. Its just: 1. Initialize the min and max of your range 2. look in the middle, is that the item you're looking for? 3. if not decide whether you go right or left 4. if right, then change max to middle -1 5. if left , then change min to middle +1 6. repeat until min > max

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.