Skip to main content
Software Engineering

Return to Question

Include crucial segment from actual code.
Source Link
Philip Kendall
Philip Kendall
  • 26.1k
  • 10
  • 67
  • 68
public static int binarySearch(ArrayList<Book> books, long searchedId) {
    if (!isSorted(books)) {
        System.err.println("ArrayList must be sorted!");
        return -1;
    }

    int ix_st = 0;
    int ix_en = books.size() - 1;
    int middle = 0;
    while (ix_st <= ix_en) {
        middle = (ix_en + ix_st)/2;
        int currId = books.get(middle).getId();
        if (currId == searchedId) {
            return middle;
        }
        if (searchedId > currId) {
            ix_st = middle + 1;
        }
        if (searchedId < currId) {
            ix_en = middle - 1;
        }
    }
    return -1;
}

public static int binarySearch(ArrayList<Book> books, long searchedId) {
    int ix_st = 0;
    int ix_en = books.size() - 1;
    int middle = 0;
    while (ix_st <= ix_en) {
        middle = (ix_en + ix_st)/2;
        int currId = books.get(middle).getId();
        if (currId == searchedId) {
            return middle;
        }
        if (searchedId > currId) {
            ix_st = middle + 1;
        }
        if (searchedId < currId) {
            ix_en = middle - 1;
        }
    }
    return -1;
}

public static int binarySearch(ArrayList<Book> books, long searchedId) {
    if (!isSorted(books)) {
        System.err.println("ArrayList must be sorted!");
        return -1;
    }

    int ix_st = 0;
    int ix_en = books.size() - 1;
    int middle = 0;
    while (ix_st <= ix_en) {
        middle = (ix_en + ix_st)/2;
        int currId = books.get(middle).getId();
        if (currId == searchedId) {
            return middle;
        }
        if (searchedId > currId) {
            ix_st = middle + 1;
        }
        if (searchedId < currId) {
            ix_en = middle - 1;
        }
    }
    return -1;
}
Post Undeleted by Celdor
Post Deleted by Celdor
Source Link
Celdor
Celdor
  • 128
  • 6

Binary search is not fast

I am trying to put in practice an algorithm for binary searching and compare it with linear searching:

  • linear search:
public static int linearSearch(ArrayList<Book> books, int searchedId) {
    for (int i = 0; i < books.size(); i++) {
        int currId = books.get(i).getId();
        if (currId == searchedId) {
            return i;
        }
    }
    return -1;
}
  • and binary search
public static int binarySearch(ArrayList<Book> books, long searchedId) {
    int ix_st = 0;
    int ix_en = books.size() - 1;
    int middle = 0;
    while (ix_st <= ix_en) {
        middle = (ix_en + ix_st)/2;
        int currId = books.get(middle).getId();
        if (currId == searchedId) {
            return middle;
        }
        if (searchedId > currId) {
            ix_st = middle + 1;
        }
        if (searchedId < currId) {
            ix_en = middle - 1;
        }
    }
    return -1;
}

the whole code

but not only is the binary searching algorithm similar but sometimes even slower than a trivial linear searching. I can't understan why. Binary search is supposed to run the code only for ~log2(100,000) = 17 iterations or ~log2(1,000,000) = 20 iterations, whilst the linear searching is full looping thorugh for 1,000,000 iterations in the worst scenario. Obviously, the lists are sorted. I've got these timings:

How many books to create?
[Me] 100000
Id of the book to search for?
[Me] 987665

Searching with linear search:
The search took 9 milliseconds.
Book not found


Seaching with binary search:
The search took 13 milliseconds.
Book not found

Process finished with exit code 0

the whole code.

I am not sure if the compiler is optimising something in background. Then it would make sense. Any idea? Thanks.

PS. The code is from the MOOC.fi website as I am taking an online course from the University of Helsinki called Java Programming I, particularly from this section.