查找List中的元素有两种方法,一个是使用contains()方法,还有一个是使用Collectoins.binarySearch()。binarySearch()方法有两种实现,一个版本是接受List和Comparator对象作为参数,另一个是接受List以及Comparable对象。这个方法使用二分查找算法来查询指定列表中的某个元素。在调用这个方法前,列表中的元素得按照它们的自然顺序进行升序排列。如果列表没有排序的话,方法调用的结果是不确定的。如果列表有多个元素与查找的元素一样,那么返回的具体是哪一个是不确定的。对于一个可”随机访问“的列表来说,算法的时间复杂度是O(log(n)。如果指定的列表没有实现RandomAccess接口并且列表长度很大的话,这个方法会基于迭代器来进行二分法的查找,它会执行O(n)次链接的遍历以及O(log n)次元素的比较。在方法的结尾,如果查找到了该元素,则返回对应元素在列表中的序号,否则返回的是(-(插入点序号)-1)。插入点的意思是这个元素应该在这个列表中的这个位置进行插入:第一个大于该查找元素的值所在的位置,如果所有元素都小于它的话则是list.size()。这意味着,当且仅当元素查找成功时,返回值才会大于等于0。List接口常见的实现比如ArrayList, Vector, CopyOnWriteArrayList和Stack都实现了RandomAccess接口,它们可以用来进行二分查找,不过还有些别的实现比如LinkedList,它没有实现RandomAccess接口,因此不适合使用二分查找。由于二分查找只能在排好序的列表中进行,因为在查找前你得先对列表排序,这可能会影响到性能,尤其是你的列表很大并且本来就无序的情况下。
下面是一段使用二分法来查找对象的程序。我们有一个包含1百万个整数的列表,这里同时使用contains()及binarySearch()方法进行搜索。
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
/** * Java program to perform binary search in Java collection e.g List, Set
[*] @author Javin Paul
[*]/
public class BinarySearchTest {
public static final Logger logger = LoggerFactory.getLogger(BinarySearchTest.class);
public static void main(String args[]) {
//creating List
List<Integer> numbers = new ArrayList<Integer>(1000000); //List of 1M records
//initializing List
for(int i =0; i<numbers.size(); i++){
numbers.add(new Integer(i));
}
//performing contains search
long startTime = System.nanoTime();
boolean isExist = numbers.contains(new Integer(1000000));
long totalTime = System.nanoTime() - startTime;
logger.info("Time to search 1Mth Record using contains() is {} nano seconds", totalTime);
//performing binary search
startTime = System.nanoTime();
Collections.sort(numbers); // List needs to be sorted for Binary Search
Integer number = Collections.binarySearch(numbers, new Integer(1000000));
totalTime = System.nanoTime() - startTime;
logger.info("Time to search 1Mth Record using binary search is {} nano seconds", totalTime);
}
}
输出结果:
2013-06-04 23:23:17,834 0 [main] INFO test.BinarySearchTest - Time to search 1Mth Record using contains() is 51404 nano seconds
2013-06-04 23:23:17,849 15 [main] INFO test.BinarySearchTest - Time to search 1Mth Record using binary search is 554261 nano seconds
从结果中可以看到,contains()方法比二分法要快了10倍,这说明使用contains()方法来搜索列表中的元素非常有效,尤其是当列表实现了RandomAccess接口的情况下。
译注:作者这么说似乎不太公平,如果列表原本就有序的话,二分查找还是相当快的,这里他是加上了排序的时间。如果排序后能进行重复利用,也还是比较划算的。
感谢网友风云无浪指出的问题,其实文中程序的列表是空的。不过修改完后该程序运行的结果仍然是相差大概10倍。当然了,这还是因为算上了排序的时间,毕竟单独从搜索的效率来说的话,二分法通常来说肯定是比顺序查找要快的。
原创文章转载请注明出处:
http://it.deepinmind.com
英文原文链接
分享到:
相关推荐
`Arrays.binarySearch()`方法可以实现这一点,但这需要确保数组已排序,否则结果可能不正确。 6. **使用Objects.equals()** - 当处理对象数组时,推荐使用`Objects.equals()`代替`==`,以处理可能的`null`值。例如...
`Arrays.binarySearch()`方法适用于有序数组,它使用二分查找算法,时间复杂度为O(log n)。但注意,对于无序数组,这种方法可能无法正确返回结果,甚至可能导致错误。 为了评估这些方法的性能,通常会进行基准测试...
Java的`Collections`类提供了多种搜索方法,如`binarySearch()`进行二分查找,以及`indexOfSubList()`在子列表中查找元素。 3. **排序算法**:为了提高搜索效率,数据通常需要先进行排序。Java中的`Arrays.sort()`...
本章涵盖了节点类(The Node Class)和二叉搜索树类(The Binary Search Tree Class)的定义,包括添加(Add)、删除(Remove)、查找(Contains)、计数(Count)以及遍历操作(Traversals),例如前序遍历...
常见的字典实现包括哈希表(Hash Table)和二叉查找树(Binary Search Tree)等。跳表是一种用于加速查找的字典实现,它通过多层链表构建,每一层都是上一层的一个子集,通过跳跃可以在较短时间内找到目标元素。 在...
二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树,其中每个节点的左子树只包含比该节点小的元素,右子树包含比该节点大的元素。 2. **红黑树**:在Java集合框架中,`TreeSet`和`TreeMap`是基于红黑树实现...
此外,Collections还有其他实用方法,如binarySearch()、reverse()等。 这些面试题涉及了Java集合框架的基础和高级用法,熟练掌握这些知识点将有助于你在面试中展现出扎实的Java基础和问题解决能力。在实际开发中,...
这样做后,我们就可以使用Java的`Collections`类提供的方法,如`contains()`或`binarySearch()`进行查找。 总结来说,理解和熟练掌握对象数组的遍历和查找对于JavaSE开发者至关重要,因为它们是构建复杂数据结构和...
为了提高空间查询的性能,Oracle Spatial提供了空间索引,如R-Tree和GIST(Generalized Indexed Search Tree)。这些索引能快速定位和比较空间对象,加速查询过程。 四、空间查询与分析 Oracle Spatial提供了丰富的...
Person类的例子中,我们可以使用Collections的`sort()`方法对列表进行排序,`equals()`方法用于判断元素是否相等,`binarySearch()`则在排序后的列表中查找元素。 7. Collections工具类:Collections提供了许多对...
`reverse(List<T> list)`反转List,`copy(List<? super T> dest, List<? extends T> src)`将一个List的内容复制到另一个List,`fill(List<T> list, T obj)`用指定对象填充整个List,`binarySearch(List...
除了基本的添加、删除和访问元素,`List<T>`还提供了一些额外的有用方法,如`Clear`清空列表,`Count`获取元素数量,`Sort`对列表进行排序,`BinarySearch`进行二分查找,`Contains`检查元素是否存在,以及`ToArray`...
标题“large_num_polygon”暗示了我们正在讨论一个与大数据量多边形图层相关的主题,尤其是在DB2数据库环境中的操作。这个图层可能包含了海量的地理空间数据,每一行记录都可能代表一个复杂的几何对象,比如城市边界...
- `BinarySearch`: 在排序的列表中搜索特定元素,返回元素的索引位置。 - `Clear`: 移除列表中的所有元素。 - `Contains`: 检查列表中是否包含特定元素。 - `ConvertAll<TOutput>`: 将列表中的元素转换为另一种类型...
二分查找尤其适用于已排序的数据,Swift的`binarySearch(_:)`函数可以实现这一操作。 3. **图论算法**:如Dijkstra算法、Floyd-Warshall算法,用于解决最短路径问题。这些算法在网络路由、交通规划等领域有广泛应用...
- **Collections类**是集合操作的工具类,提供了一组静态方法来操作集合,如`sort()`, `reverse()`, `binarySearch()`等。 - **Set接口实现类**,如`HashSet`提供无序且不重复的元素集合,`TreeSet`则通过红黑树...
- `binarySearch(T[] a, T key)`:在已排序的数组中查找指定元素的位置。 - `copyOf(T[] original, int newLength)`:创建一个新的数组,其长度为 `newLength`,并将原数组的元素复制到新数组中。 - `copyOfRange...
- **方法1-1**: 使用`Arrays.sort()`和`Arrays.binarySearch()`。首先对数组进行排序,然后使用二分查找法来确定元素是否存在。这种方法适用于可排序的元素,效率较高,时间复杂度为O(log n)。 - **方法1-2**: ...
二叉搜索树(Binary Search Tree,BST)是一种特殊的二叉树,它的每个节点都包含一个键值对,左子树的键值都小于根节点的键值,右子树的键值都大于根节点的键值。二叉搜索树的主要操作包括查找、插入和删除。 查找...