binarySearch与IndexOf的那些事儿~

binarySearch与IndexOf的那些事儿~

binarySearch与IndexOf的那些事儿~

大家好,我是雄雄,今天我们来看看java中的binarySearch方法

我们都知道,如果我们想要在一个集合中查找某个元素所在的位置时,可以使用list类自带的indexOf方法,简单方便还快捷。不过,Collections类也给我提供了个查找集合中元素的方法——binarySearch,但是这个方法和indexOf方法无论从检索原理还是返回值上来说,都有很大的差距!

01

IndexOf方法

我们先来看看indexOf是怎么检索集合内元素的,示例代码如下:

public static void main(String[] args) {

              Listlists = new ArrayList();

              lists.add(3);

              lists.add(6);

              lists.add(8);

              lists.add(7);

              lists.add(1);

              System.out.println("集合中的元素:");

              for (Integer str : lists) {

                     System.out.print(str+" ");

              }

              int index = lists.indexOf(2);

              System.out.println("\n2所在的位置是:"+index);

       }

其运行结果:

binarySearch与IndexOf的那些事儿~

下面我们再来查找一下“8”所在的位置,稍微改一下代码:

int index = lists.indexOf(8);

其运行结果如下:

binarySearch与IndexOf的那些事儿~

两个案例说明不了问题,我们再来一个,比如查找一下“4”

binarySearch与IndexOf的那些事儿~

这下很清楚,使用indexOf方法查找集合中的元素,简单方便,如果有,返回该元素的下标(下标从0开始),如果没有,则返回的是-1。

02

binarySearch方法

binarySearch方法采用二分法的方式来对集合元素进行检索,二分法搜索说的简单点,就是“折半折半再折半”!简单,而且在效率方面要比idnexOf的方法要高出不少!下面我们就来看看binarySearch方法是如何检索数据的。

首先,需要说明的是,使用binarySearch方法检索(二分法)的前提是要对集合内数据进行排序,否则返回的值是不准确的!要是不排序,怎么能知道值是在比中间值小的区域或者比中间值大的区域呢?

下面我们使用代码来看看:

public static void main(String[] args) {

              Listlists = new ArrayList();

              lists.add(3);

              lists.add(6);

              lists.add(8);

              lists.add(7);

              lists.add(1);

              // 原来的集合

              System.out.println("原来的集合:");

              for (Integer str : lists) {

                     System.out.print(str + " ");

              }



              // 对集合进行排序

              Collections.sort(lists);

              System.out.println("\n排序后的集合:");

              for (Integer str : lists) {

                     System.out.print(str + " ");

              }


              // 使用binarySearch方法查找集合中的元素

              int i = Collections.binarySearch(lists, 2);

              System.out.println("\n2所在的位置:" + i);



       }

代码分析:集合还是原来的集合,只是我们将集合进行了简单的升序,然后使用binarySearch方法查找集合中“2”所在的位置,indexOf方法返回的是-1,那binarySearch方法呢?

运行结果如下:

binarySearch与IndexOf的那些事儿~

居然是-2,结果我们先保留着,我们在继续举例!如果查找“8”呢,结果如下:

binarySearch与IndexOf的那些事儿~

结果是4,那我们在继续查找“4”所在的位置,其结果如下所示:

binarySearch与IndexOf的那些事儿~

好了,到这里已经差不多可以总结了,有同学可能会说:“老师,这没有规律的一些返回值,怎么总结?”别着急,我们挨个来看!

01

分析1:查找“2”时,显然集合中没有“2”,所以必然找不到,但是返回值-2又改怎么解释呢?大家注意看,2如果有的话,应该在哪个位置?是不是在3的位置(排序后),大于1小于3,那3所在的位置和“-2”有何关联吗?当你把整个集合的下标设成从1开始,3所在的位置即2,因为没有“2”这个元素,所以返回值就是“-2”。

02

分析2:查找“8”时,集合中是存在的,返回值是4,大家把现在“8”的位置和返回值4进行关联,总结一下是什么?那就是,当集合中存在该数时,下标是从0开始的,并且值是正数。

03

分析3:带着分析1的结论,我们来验证一下查找“4”。集合中是不存在4的,那如果有的话,“4”应该在6的位置,那下标从1开始,“6”所在的位置就是3,又因为集合中没有,所以是负数!

以上就是关于indexOf和binarySearch方法的总结,是不是庆幸自己又学会了一点啦!

往期精彩

新机必装!那些你不知道的实用技软件在这里!文末免费获取

2020-10-31

binarySearch与IndexOf的那些事儿~

自从有了这款辣椒酱,拌饭再也不用老干妈

2020-10-30

binarySearch与IndexOf的那些事儿~

如何使用bootstrap实现轮播图?

2020-10-29

binarySearch与IndexOf的那些事儿~

班级日常分享:一天一瞬间!

2020-10-29

binarySearch与IndexOf的那些事儿~

中流击水,浪遏飞舟

2020-10-28

binarySearch与IndexOf的那些事儿~

王宝兴:秋运会

2020-10-27

binarySearch与IndexOf的那些事儿~

高启航:秋运会!

2020-10-26

binarySearch与IndexOf的那些事儿~

binarySearch与IndexOf的那些事儿~

binarySearch与IndexOf的那些事儿~

点分享

binarySearch与IndexOf的那些事儿~

点点赞

binarySearch与IndexOf的那些事儿~

点在看

上一篇:查找


下一篇:<查找算法> 二分查找BinarySearch