Java中的binarySearch方法

「爱情、让人受尽委屈。」 2022-11-21 11:53 149阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MTM3Mzk3_size_16_color_FFFFFF_t_70_pic_center]

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

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

## IndexOf方法 ##

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

public static void main(String[] args) {
    		List<Integer> lists = new ArrayList<Integer>();
    		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);
    		
    	}

其运行结果：  
![在这里插入图片描述][20201101190630363.png_pic_center]  
下面我们再来查找一下“8”所在的位置，稍微改一下代码：  
int index = lists.indexOf(8);  
其运行结果如下：  
![在这里插入图片描述][20201101190652342.png_pic_center]

两个案例说明不了问题，我们再来一个，比如查找一下“4”  
![在这里插入图片描述][20201101190700546.png_pic_center]

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

## binarySearch方法 ##

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

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

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

public static void main(String[] args) {
    		List<Integer> lists = new ArrayList<Integer>();
    		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方法呢？  
运行结果如下：

![在这里插入图片描述][20201101190749245.png_pic_center]  
居然是-2，结果我们先保留着，我们在继续举例！如果查找8呢，结果如下：  
![在这里插入图片描述][20201101190809328.png_pic_center]  
结果是4，那我们在继续查找“4”所在的位置，其结果如下所示：  
![在这里插入图片描述][20201101190821608.png_pic_center]  
好了，到这里已经差不多可以总结了，有同学可能会说：“老师，这没有规律的一些返回值，怎么总结？”别着急，我们挨个来看！

分析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方法的总结，是不是庆幸自己又学会了一点啦！

欢迎大家关注我公众号雄雄的小课堂呢！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MTM3Mzk3_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/bd66d7e8ce2744d68d876a3530687f36.png
[20201101190630363.png_pic_center]: /images/20221120/9d7555cc80b04e38ba1fe1443284afa0.png
[20201101190652342.png_pic_center]: https://img-blog.csdnimg.cn/20201101190652342.png#pic_center
[20201101190700546.png_pic_center]: https://img-blog.csdnimg.cn/20201101190700546.png#pic_center
[20201101190749245.png_pic_center]: https://img-blog.csdnimg.cn/20201101190749245.png#pic_center
[20201101190809328.png_pic_center]: https://img-blog.csdnimg.cn/20201101190809328.png#pic_center
[20201101190821608.png_pic_center]: https://img-blog.csdnimg.cn/20201101190821608.png#pic_center