源码|【java_基础深入】JDK借助RandomAccess接口，定制ArrayList与LinkedList的二分查找策略 java|算法

java常用集合类接口实现情况

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable

RandomAccess 接口 ArrayList 和 LinkedList 共同实现了空接口 Cloneable Serializable
ArrayList 独有的空接口 RandomAccess，这个空接口起的是一个标记的作用，具体用处看以下代码
查看Collections 中的代码binarySearch()

public static int binarySearch(List list, T key, Comparator c){}

读注释
binarySearch 二分查找法是什么

/** * Searches the specified list for the specified object using the binary * search algorithm.The list must be sorted into ascending order * according to the specified comparator (as by the * {@link #sort(List, Comparator) sort(List, Comparator)} * method), prior to making this call.If it is * not sorted, the results are undefined.If the list contains multiple * elements equal to the specified object, there is no guarantee which one * will be found. */

二分查找法是对一个有序序列，进行查找，时间复杂度是O（logN）
以下是Collections.binarySearch (...) 的第一段注释，也说得很清楚，参与二分查找的序列必须是有序的
binarySearch 使用 RandomAccess 的动机是什么

/** *This method runs in log(n) time for a "random access" list (which * provides near-constant-time positional access).If the specified list * does not implement the {@link RandomAccess} interface and is large, * this method will do an iterator-based binary search that performs * O(n) link traversals and O(log n) element comparisons. */

该空接口有标识作用，第二段注释有点绕。意思是：实现了RandomAccess接口的List, 如ArrayList，能稳定得满足O(logn)的时间复杂度完成搜索。而LinkedList 需要有O(n)的时间复杂度用于遍历，加上 O(logn) 的时间复杂度用于比较。换言之，LinkedList 的二分查找效率是O(nlogn)。
内在原因：
ArrayList.get(index)时间复杂度：O(1)
LinkedList.get(index)时间复杂度：O(n) 。后文将说道如何优化这个O(n)的复杂度
基于ArrayList的下标，寻找value:16的下标 【源码|【java_基础深入】JDK借助RandomAccess接口，定制ArrayList与LinkedList的二分查找策略】ArrayList是存在下标的，存在以下有序序列

value	1	5	7	8	11	15	16	28	39
index	0	1	2	3	4	5	6	7	8

根据数组长度 mid 确认为 4，get(4) == 11 < 16
根据二分算法mid 确认为 6，get(6) == 16，返回值就是下标：6

相关代码，省略get(index)代码：

private static int indexedBinarySearch(List> list, T key) { int low = 0; int high = list.size()-1; while (low <= high) { int mid = (low + high) >>> 1; Comparable midVal = list.get(mid); int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found }

使用get(ListIterator i, int index) 优化遍历

value	1	5	7	8	11	15	16	28	39
迭代器下标	0	1	2	3	4	5	6	7	8

基于LinkedList，寻找value:16的下标，无下标。
尽管LinkedList可取得链表总长度，但是每次LinkedList.get(index)操作都会让双链表从某一端从头遍历
为了解决每次从头遍历的问题，JDK开发者使用ListIterator 来找index对应的value。
ListIterator 可以向前遍历，也可以向后遍历

private static T get(ListIterator i, int index) { T obj = null; // 待返回的value int pos = i.nextIndex(); // 向后移动游标获取当前位置 if (pos <= index) { // 当前位置小于index do { obj = i.next(); } while (pos++ < index); // 一直向后找，直到到达index的位置，返回index对应的value } else { do { obj = i.previous(); // 反之向前找 } while (--pos > index); } return obj; }

有了get(ListIterator i, int index) ，就可以完成下面的搜索过程了

基于LinkedList ，寻找value:16的下标

根据链表长度 mid 确认为 4，此时listIterator 的游标为0
1.1 从0开始，往后一个一个找，get(listIterator，4) == 11 < 16; 返回值对应的value：11
11 < 16。mid确认为6。发现游标往后才有可能找到目标元素，如果用LinkedList.get(mid)，还要从头遍历，好在有get(ListIterator i, int index)，可以从5开始找
2.1 == 从5开始==，往后一个一个找
2.2 get(listIterator， 6) == 16 ,返回值对应i的value:：16
很幸运，16 为待寻找元素，返回值为mid：5

private static int iteratorBinarySearch(List> list, T key){int low = 0; int high = list.size()-1; ListIterator> i = list.listIterator(); while (low <= high) { int mid = (low + high) >>> 1; Comparable midVal = get(i, mid); // int cmp = midVal.compareTo(key); if (cmp < 0) low = mid + 1; else if (cmp > 0) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found }

结论 RandomAccess 接口只参与标记作用，目的是让ArrayList发挥其底层数据结构数组的O(1)查找能力
同时又没有放弃LinkedList，使用用ListIterator 避免LinkedList从头开始遍历。
以上也侧面说明了以下代码是个很低效的代码

LinkedList linkedList = new LinkedList(); for(int i = 0; i < linkedList.size(); i++) { System.out.println(linkedList.get(i); }

写成高效的，就是foreach循环的本质。

LinkedList linkedList = new LinkedList(); ListIterator listIterator = linkedList.listIterator(); // 只往后遍历可以写成iterator() while (listIterator.hasNext()) { listIterator.next(); }