java中的数组二分法

2018-06-18 01:19:21来源：未知阅读 ()

数组二分法意在以较快的速度查找到某个值的下标位置。

二分法的核心思想：找到一个数组的中间位置值，判断某个数值是在这个中间值的左边还是右边，如果是左边，将中间位置之前进行二分，二分后，结束位置变为原始中间位置。如果是右边，将中间位置之后进行二分，二分后，开始位置变为原始中间位置。

废话不多说，先上代码。

/**
	 * 数组二分法
	 */
	@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{
					after=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;
	}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有