binarySearch与IndexOf的那些事儿~

ゝ一纸荒年。 2022-12-25 02:48 226阅读 0赞

![format_png][]

![format_png 1][]

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

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

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);
    
           }

其运行结果：

![format_png 2][]

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

int index = lists.indexOf(8);

其运行结果如下：

![format_png 3][]

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

![format_png 4][]

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

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**方法呢？

运行结果如下：

![format_png 5][]

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

![format_png 6][]

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

![format_png 7][]

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

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

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

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

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

**往期精彩**

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

[2020-10-31][Link 1]

[![format_png 8][] ][Link 1]

[自从有了这款辣椒酱，拌饭再也不用老干妈][Link 2]

[2020-10-30][Link 2]

[![format_png 9][] ][Link 2]

[如何使用bootstrap实现轮播图？][bootstrap]

[2020-10-29][bootstrap]

[![format_png 10][] ][bootstrap]

[班级日常分享：一天一瞬间！][Link 3]

[2020-10-29][Link 3]

[![format_png 11][] ][Link 3]

[中流击水，浪遏飞舟][Link 4]

[2020-10-28][Link 4]

[![format_png 12][] ][Link 4]

[王宝兴：秋运会][Link 5]

[2020-10-27][Link 5]

[![format_png 13][] ][Link 5]

[高启航：秋运会！][Link 6]

[2020-10-26][Link 6]

[![format_png 14][] ][Link 6]

![format_png 15][]

![format_png 16][]

点分享

![format_png 17][]

点点赞

![format_png 18][]

点在看

[format_png]: /images/20221120/1bd40b892b1442359605fc78f3a2c3ea.png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9EWjlUaWF4ZFF4azE0V0lHaWNBSWtEdGZLZVFQYXVHb2huM3k2NFhTaWI0YjhUWEtYNWxyWEN4SWozcjN3UzE5anlXUk5EN3NGVVJmdjdycGRBaWFEVThEVEEvNjQw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9EWjlUaWF4ZFF4azE0V0lHaWNBSWtEdGZLZVFQYXVHb2huRmdxTGJvdmg2R0lUMU1ic3VMUGljRDFrWWliTXhqU0w2dnNpY1BRYk8zS2cwSlJ0NTJGUlFsaWJFZy82NDA?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9EWjlUaWF4ZFF4azE0V0lHaWNBSWtEdGZLZVFQYXVHb2huYzNQSzI5dWdoMVdpYjBQOUVweENwME9pY3hraWFGQzZPMjVBWmJZSVpFNnkxend6ODRrcVFrYmtRLzY0MA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9EWjlUaWF4ZFF4azE0V0lHaWNBSWtEdGZLZVFQYXVHb2huWktONkZwN2hhb01LOWZwaWM2S0RnWXFjazVmT3d6WjRKZkpjYVFCUTFPRkhjeTdvamlhOGRTaWF3LzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9EWjlUaWF4ZFF4azE0V0lHaWNBSWtEdGZLZVFQYXVHb2huWjFIOWo2N0Q1YXdwbGtqV1M4R3AyRFZRd1Y5MFNDMVJodFhWZ3pkWTFzUTdMQ3UyaWJmQkp6QS82NDA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9EWjlUaWF4ZFF4azE0V0lHaWNBSWtEdGZLZVFQYXVHb2huZm9Kd2ljU1FJd0NpY3czalRKSTlZb0FtRWZXbzFLYVBpY1E1ZUJOcTdsTGtQM2tIaWJGTnRyTEV5Zy82NDA?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9EWjlUaWF4ZFF4azE0V0lHaWNBSWtEdGZLZVFQYXVHb2huYWljVEpWZ1N4M2I0b09pYzR1OGZlS3oyd1FLb2RlaWFiT1dTeUlHS2ZwaWNjM05IcmZDRUE4Y09aQS82NDA?x-oss-process=image/format,png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzIxNjE1ODA5NA%3D%3D&chksm=978fef43a0f866559246d6b1a44235025fe3c6658b9ae3ae5ad0c281fcb590e6e7f90c568e50&idx=1&mid=2247497122&scene=21&sn=9e3f76c4bcf2b1613de1e2d478130790#wechat_redirect
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9EWjlUaWF4ZFF4azNTa0c2bDZ2aWNEV3JQbHR4c2VsWFZTcm9RaFhZTUhsR2lhNFRtUGpyV2ozYmExeGlhTDVsVHpRRkIxdDNpYjF5UndIdmZ5TlhKN2VpYVJ3US82NDA?x-oss-process=image/format,png
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzIxNjE1ODA5NA%3D%3D&chksm=978fef7da0f8666b66e75eef8907fb9a9e8e55a0ea9a2fd87cc986259f3c3866c05c77aaab98&idx=1&mid=2247497116&scene=21&sn=c72b9c0f8d08612b1187bf31d42c8e31#wechat_redirect
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9EWjlUaWF4ZFF4azFHeDYwZG1TYk5BVDdJM2pNU25sdzdxWGliTzR5aWJpYlpWRUVvaWJJTlByNFZIeVIzU1R4a09iWmdkS3V5SnFkZXp0RlNkcTN1aWFkdGljRkEvNjQw?x-oss-process=image/format,png
[bootstrap]: http://mp.weixin.qq.com/s?__biz=MzIxNjE1ODA5NA%3D%3D&chksm=978fef66a0f86670e227bf586ba840d0472375dc3649e3e344dd5d83909636f30d9bdc3f48e5&idx=1&mid=2247497095&scene=21&sn=00a48378c3447b28c7b22de2c005ef1f#wechat_redirect
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9EWjlUaWF4ZFF4azNKU2N6MmdIeVdhdldUTHFkeUs5Rjd0bXVXYkk1ZWROc3RnbEw5NEZQc0VhVXRBR2liZGliSUJpY2xDcDJ1cjFtNXNsVlI1ajYzMHk2eVEvNjQw?x-oss-process=image/format,png
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzIxNjE1ODA5NA%3D%3D&chksm=978fef66a0f8667062e2e7c8be7c13a75a73e029c8a35635c41ca80680e5f7fb8dc2d973d998&idx=2&mid=2247497095&scene=21&sn=8d22cb8183ae274c8c64712be2fb5d41#wechat_redirect
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9EWjlUaWF4ZFF4azNKU2N6MmdIeVdhdldUTHFkeUs5RjdhODVob2ljeTVobFdpYzBlZGRIWGdYR1pIUlJpYUNaWmNYeDV3WUlFN2N0MzJGRlRvV0ZRUURVTWcvNjQw?x-oss-process=image/format,png
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzIxNjE1ODA5NA%3D%3D&chksm=978feff1a0f866e7504fbc0e5596403ad11a6922d6525a3b9667452dd04bd9afd56637b61bd6&idx=1&mid=2247496976&scene=21&sn=d57b6c1e0895ea16a66c61feacadb5a8#wechat_redirect
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9EWjlUaWF4ZFF4azBmTG5md2RyV0FvUmg0aWJ2UEVhN2liV000NjZTdHNTY2w3enk1amZIN2NHenVqaWJTNWljMVFRd2R1VmhNeld4c2liakwxRGp5b216U0h6QS82NDA?x-oss-process=image/format,png
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzIxNjE1ODA5NA%3D%3D&chksm=978fee35a0f86723e1a82435ada131c3e506cd858c28292c12ea8d43d8775ea622aacfd35d84&idx=1&mid=2247496916&scene=21&sn=de2c12f1bba44c43d6bc686284dcd713#wechat_redirect
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9EWjlUaWF4ZFF4azE0VzdqM3RtVG5sbWpNNnkwaWFpY2dCamxUeHlpYlBpYk1oOE96VjA2cDJ2YjM2TkNZOEtDM3ZvWUJINmZ5TXpDaWE0UEhiRzFwd25naWFFbGcvNjQw?x-oss-process=image/format,png
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzIxNjE1ODA5NA%3D%3D&chksm=978fee6fa0f86779b4773ff11f7f4a86fe1a3a6e47246f443bf4567d615b8ed16e0e4aed6452&idx=1&mid=2247496846&scene=21&sn=7a3f621faa0802e858d3ee15fecff4cc#wechat_redirect
[format_png 14]: /images/20221120/8d244d7daa464497b75354b66affb5d7.png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9EWjlUaWF4ZFF4azFGUjZ5MEEzaWFxZDJDTENGMzNGMXg0dDZBTVYwQW1ENnRMUzNmSXZTMmJvZkxLZURnbVR6dVA0WVM5QndFVzBVWDRHZlhJd2liZ0tqQS82NDA?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9EWjlUaWF4ZFF4azFPclNvckhkaWM4dlRXMmVWbFpSUzVaOGUxcUJpY2xGMEo3UzE1WmgzOEtzejRlTWliaWJzQVl4ajF5ZEZrNmliQlBBdFN3c3BpYjVETmliMUZRLzY0MA?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9EWjlUaWF4ZFF4azFPclNvckhkaWM4dlRXMmVWbFpSUzVaZE1rWUVJUTY4bWF6YWxLTkxZUFdtWDZ0Y2d2RjZpYjhnZ3pxMTVNUER5aWFaR3hxeGxSaWJNMDhnLzY0MA?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9EWjlUaWF4ZFF4azFPclNvckhkaWM4dlRXMmVWbFpSUzVaRTVpY3RyS0JvYWlid0l4aWNack11RE9YM0J6c0dPaExMWWdqMFM1NHVITGliREt2VGZqbktGOE9xQS82NDA?x-oss-process=image/format,png