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

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

i know 1 use. have list of students. want search pupil name. till doing manually iterating list below

for(int = 0; < list.size(); i++) { pupil student = list.get(i); if(student.getname().equals(studentnameiwanttosearch)) { index = i; break; } } pupil student = list.get(index); //my logic here

recently saw method named binarysearch(list<? extends t> list, t key, comparator<? super t> c) collections class. read this. in order perform binary search, list has sorted , has passed binarysearch method argument.

now, if don't want sort list? because don't need sorting on it. see sorting additional overhead on logic.

can please tell me why should utilize binary search instead of manually searching. know binary search takes o(log n) time. manually searching takes o(n). concerned sorting also. sorting whole list takes time. unfortunately don't know algorithm java uses. hope java uses best available algorithm sorting. still want know.

thank in advance.

binary search way faster normal search.

suppose have list 11 elements: a, c, d, f, g, j, m, p, r, s, z. loop iterate on elements, minimum of 1 iteration , maximum of 11 iterations, makes average of 5.5 iterations find element. let's seek pick r list. way binary search works this: pick middle element (in our case j). r > j, r's index greater j's. let's again, middle element m z. that's r, we're there.

you see have less iterations, average. per iteration, half of elements remain.

that's advantage of binary search. drawback list must sorted. if alter list lot, need sort inserted element, , using binary search might 'expensive'. otherwise, if search lot, might want utilize binary search.

java collections