What is the performance of Collections.binarySearch over manually searching a list?

Question

I would like to know the which one to use. I have a list of students. I want to search a student with his name. Till now I was doing it manually by iterating the list like below

for(int i = 0; i < list.size(); i++) {
    Student student = list.get(i);
    if(student.getName().equals(studentNameIWantToSearch)) {
        index = i;
        break;
    }
}

Student student = list.get(index);
//my logic from here

Recently I saw a method named binarySearch(List<? extends T> list, T key, Comparator<? super T> c) from Collections class. I read about this. In order perform a binary search, the list has to be sorted and the has to be passed to binarySearch method as an argument.

Now, what if I don't want to sort the list? Because I don't need sorting on it. I see sorting as an additional overhead on my logic.

Can anyone please tell me why should I use binary search instead of manually searching. I know that binary search takes O(log n) time. Manually searching it takes O(n). I am concerned about the sorting also. Sorting the whole list also takes some time. Unfortunately I don't know what algorithm does java uses. I hope java uses the best available algorithm for sorting. But still I want to know.

Thank you all in advance.

Answer 1

Binary search is way faster than normal search.

Suppose you have a list with 11 elements: a, c, d, f, g, j, m, p, r, s, z. Your for loop to iterate over the elements, with a minimum of 1 iteration and a maximum of 11 iterations, which makes an average of 5.5 iterations to find an element. Now let's try to pick r from the list. The way binary search works is this: pick the middle element (in our case j). r > j, thus r's index is greater than j's. Let's do it again, the middle element from m to z. That's r, we're already there.

You see that we have less iterations, by average. Per iteration, a half of the elements remain.

That's the advantage of binary search. The drawback is that the list must be sorted. So if you change the list a lot, then you need to sort the inserted element, and then using binary search might be too 'expensive'. Otherwise, if you search a lot, you might want to use binary search.