[转载] Java 中的binarySearch方法

参考链接: Java中的二分搜索binarySearch

Java提供了一个操作Set 、 List和Map等集合的工具类:Collections,该工具类里提供了大量方法对集合元素进行排序、查询和修改等操作,下面要说的就是查询操作中的binarySearch方法。 

首先创建一个list集合,代码如下: 

List<Integer> list = new ArrayList<>(); 

        list.add(6); 

        list.add(1); 

        list.add(5); 

        list.add(3); 

        list.add(4); 

        list.add(2); 

System.out.println(list); 

输出结果如图: 

 

1、binarySearch(List list, T key):使用二分搜索法搜索指定列表,第一个参数是列表,第二个参数是要查找的元素,返回的是要查找的元素的索引。只有排序后的List集合才可用二分法查询元素的索引,而且List集合的排序(升序或降序)要和binarySearch的排序(升序或降序)一致,不然返回的索引不准确。 

例如:直接对这个列表使用binarySearch方法,查找元素3在这个集合中的索引位置。代码如下: 

int intA = Collections.binarySearch(list, 3); 

System.out.println("list集合:" + list); 

System.out.println("3在集合中的索引位置:" + intA); 

返回的索引不正确,结果如下: 

 

但是在对列表进行升序排序之后,结果就不一样了: 

Collections.sort(list);  // sort()这个方法用来升序排序; 

int intB = Collections.binarySearch(list, 3); 

System.out.println("list集合:" + list); 

System.out.println("3在集合中的索引位置:" + intB); 

由于binarySearch方法默认的是升序排序,所以与列表的排序一致,返回的索引正确,结果如下,: 

 

2、binarySearch(List list, T key,Comparator c):比上面多了一个参数,这个参数是用来自定义排序规则的,如果自定义了降序排序,则list集合也要降序排序,否则返回的索引不准确,要保证List集合的排序和binarySearch方法的排序一致。 

Collections.reverse(list);// reverse()反转顺序,之前是升序则反转后是降序 

      System.out.println("list集合:" + list); 

      int a = Collections.binarySearch(list, 5, new Comparator<Integer>() { 

            @Override 

            public int compare(Integer o1, Integer o2) { 

                // 从大到小(即降序排序) 

                return o2 - o1; 

            } 

        }); 

返回的索引正确,结果如下:

上一篇:自己实现的BinarySearch


下一篇:java进阶(11)--Arrays工具类