How does Java perform binary searches on arrays and lists?

"The Arrays class provides public static <T> int binarySearch(T[] a, T key, Comparator<T> c). That is, it takes an array of elements as well as key and a Comparator all of the same type T. It returns an integer representing the index at which it finds the first matching element (there is no guarantee that the first element in the sorted list is returned). If no match is found, then the method returns something negative. It actually returns a negative value corresponding to the insertion point at which the element would be if it had existed. Another version has the same behavior but can be called without a Comparator, relying instead on the natural ordering of elements. For this variation, the type of elements must implement the Comparable interface. The Collections class provides a similar method, public static <T> int binarySearch(List<T> list, T key, Comparator<T> c). The only difference is that the method takes a List instead of an array. Otherwise, the behavior is the same. We present several examples in Code Sample 36.1.\n\nArrayList<Student> roster = ...\n\nStudent castroKey = null;\n\nint castroIndex;\n\n//create a \"key\" that will match according to the\n\n// Student.equals() method\n\ncastroKey = new Student(\"Starlin\", \"Castro\", 131313, 3.95);\n\ncastroIndex = roster.indexOf(castroKey);\n\nSystem.out.println(\"at index \" + castroIndex + \": \" +\n\nroster.get(castroIndex));\n\n//create a key with only the necessary fields to match\n\n// the comparator\n\ncastroKey = new Student(\"Starlin\", \"Castro\", 0, 0.0);\n\n//sort the list according to the comparator\n\nCollections.sort(roster, byName);\n\ncastroIndex = Collections.binarySearch(roster, castroKey, byName);\n\nSystem.out.println(\"at index \" + castroIndex + \": \" +\n\nroster.get(castroIndex));\n\n//create a key with only the necessary fields to match\n\n// the comparator\n\ncastroKey = new Student(null, null, 131313, 0.0);\n\n//sort the list according to the comparator\n\nCollections.sort(roster, byId);\n\ncastroIndex = Collections.binarySearch(roster, castroKey, byId);\n\nSystem.out.println(\"at index \" + castroIndex + \": \" +\n\nroster.get(castroIndex));\n\nCode Sample 36.1.: Java Search Examples"