如何使用二分法查找(java,web开发)

1、二分法查找的背景

当数组或者集合中存放的元素数量非常多的时候，想要跟踪具体某个元素的位置或者是否存在，常规方式是循环每一个元素直到找到要查找的元素为止。这样的查找方式效率非常低下，这个时候需要使用二分法来实现，提高查找效率。

2、二分法查找的介绍

二分法查找(折半查找)，找指定数值所在的位置

百度百科是这样介绍二分法查找的：

3、二分法查找的算法思想

假设数组是按升序排序的，对于给定的目标值aim，从数组的中间位置开始查找：1.若查找数据与中间元素值正好相等，则返回中间元素值的索引;2.若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围;3.若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围;注：查找成功返回索引，失败返回-1

4、代码实现

4.1 利用循环的方式实现二分法查找

publicclassBinarySearch{publicstaticvoidmain(String[]args){//生成一个随机数组int[]array=suiji();//对随机数组排序Arrays.sort(array);System.out.println("产生的随机数组为："+Arrays.toString(array));System.out.println("要进行查找的值：");Scannerinput=newScanner(System.in);//进行查找的目标值intaim=input.nextInt();//使用二分法查找intindex=binarySearch(array,aim);System.out.println("查找的值的索引位置："+index);}/***生成一个随机数组**@return返回值，返回一个随机数组*/privatestaticint[]suiji(){//random.nextInt(n)+m返回m到m+n-1之间的随机数intn=newRandom().nextInt(6)+5;int[]array=newint[n];//循环遍历为数组赋值for(inti=0;i<array.length;i++){array[i]=newRandom().nextInt(100);}returnarray;}/***二分法查找---循环的方式实现**@paramarray要查找的数组*@paramaim要查找的值*@return返回值，成功返回索引，失败返回-1*/privatestaticintbinarySearch(int[]array,intaim){//数组最小索引值intleft=0;//数组最大索引值intright=array.length-1;intmid;while(left<=right){mid=(left+right)/2;//若查找数值比中间值小，则以整个查找范围的前半部分作为新的查找范围if(aim<array[mid]){right=mid-1;//若查找数值比中间值大，则以整个查找范围的后半部分作为新的查找范围}elseif(aim>array[mid]){left=mid+1;//若查找数据与中间元素值正好相等，则放回中间元素值的索引}else{returnmid;}}return-1;}}

代码执行结果：

产生的随机数组为：[16,33,40,46,57,63,65,71,85]要进行查找的值：46查找的值的索引位置：3

若输入的值找不到，则返回-1

产生的随机数组为：[28,41,47,56,70,81,85,88,95]要进行查找的值：66查找的值的索引位置：-1

4.2 利用递归的方式实现二分法查找

publicclassBinarySearch3{publicstaticvoidmain(String[]args){//生成一个随机数组int[]array=suiji();//对随机数组排序Arrays.sort(array);System.out.println("产生的随机数组为："+Arrays.toString(array));System.out.println("要进行查找的值：");Scannerinput=newScanner(System.in);//进行查找的目标值intaim=input.nextInt();//使用二分法查找intindex=binarySearch(array,aim,0,array.length-1);System.out.println("查找的值的索引位置："+index);}/***生成一个随机数组**@return返回值，返回一个随机数组*/privatestaticint[]suiji(){//Random.nextInt(n)+m返回m到m+n-1之间的随机数intn=newRandom().nextInt(6)+5;int[]array=newint[n];//循环遍历为数组赋值for(inti=0;i<array.length;i++){array[i]=newRandom().nextInt(100);}returnarray;}/***二分法查找---递归的方式**@paramarray要查找的数组*@paramaim要查找的值*@paramleft左边最小值*@paramright右边最大值*@return返回值，成功返回索引，失败返回-1*/privatestaticintbinarySearch(int[]array,intaim,intleft,intright){if(aim<array[left]||aim>array[right]){return-1;}//找中间值intmid=(left+right)/2;if(array[mid]==aim){returnmid;}elseif(array[mid]>aim){//如果中间值大于要找的值则从左边一半继续递归returnbinarySearch(array,aim,left,mid-1);}else{//如果中间值小于要找的值则从右边一半继续递归returnbinarySearch(array,aim,mid+1,array.length-1);}}}

递归相较于循环，代码比较简洁，但是时间和空间消耗比较大，效率低。在实际的学习与工作中，根据情况选择使用。