java中的数组二分法
程序员文章站
2022-07-07 08:25:39
数组二分法意在以较快的速度查找到某个值的下标位置。 二分法的核心思想:找到一个数组的中间位置值,判断某个数值是在这个中间值的左边还是右边,如果是左边,将中间位置之前进行二分,二分后,结束位置变为原始中间位置。如果是右边,将中间位置之后进行二分,二分后,开始位置变为原始中间位置。 废话不多说,先上代码 ......
数组二分法意在以较快的速度查找到某个值的下标位置。
二分法的核心思想:找到一个数组的中间位置值,判断某个数值是在这个中间值的左边还是右边,如果是左边,将中间位置之前进行二分,二分后,结束位置变为原始中间位置。如果是右边,将中间位置之后进行二分,二分后,开始位置变为原始中间位置。
废话不多说,先上代码。
/** * 数组二分法 */ @Test public void test(){ int[] array={1,2,3,4,5,6,7,8,9,10}; int sum=0; String value=binary1(array,9,sum); System.out.println("所要查找数据的位置:"+value);//返回下标位置 } /* * 二分法第一种(自己写的) */ public String binary1(int[] array,int value,int sum){ int before=0; int after=array.length-1; while(before<=after){//eg,查询9这个数的下标,循环了两次 sum++; int mid=(before+after)/2; if((before+after)%2!=0){ mid+=1; } if(value==array[mid]){ return mid+"--"+sum; }else{ if(value>array[mid]){ before=array[mid]; }else{ before=array[mid]; } } } return null; } /* * 二分法第二种(网上查的) */ public static String binary(int[] array,int value,int sum){ int low=0; int high=array.length-1; while(low<=high){//eg,查询9这个数的下标,循环了三次 sum++; int middle=(low+high)/2; // System.out.println(middle); if(value==array[middle]){ return middle+"--"+sum; } if(value>array[middle]){ low=middle+1; } if(value<array[middle]){ high=middle-1; } } return null; }