- //正常的二分搜索 复杂度为O(logn)就无需细究了
- //我们来看迭代器的二分搜索实现
- private static int iteratorBinarySearch(Listextends Comparablesuper T >> list, T key) {
- int low = 0;
- int high = list.size() - 1;
- ListIteratorextends Comparablesuper T >> i = list.listIterator();
- while (low <= high) {
- int mid = (low + high) >>> 1;
- Comparablesuper T > midVal = get(i, mid); //这里用了一个get方法
- 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
- }
来源: http://www.bubuko.com/infodetail-1862754.html