经典案例,二分查找的三种实现方式 (二)
重新构建数组,或者在参数上确定数组下标范围，所以我们使用下标来确定
public static boolean binarySearchWithRecursion(int[] array ,int start,int end ,int val)
{
// 每次递归，都把start赋值为0 这样不合理
// start = 0;
// end = array.length-1;
int middle = (start+end)/2;
if(val > array[end] || val < array[start])
{
searchError(val);
return false;
}
if(val == array[middle])
{
searchOk(val, middle);
return true;
}
// val 在右侧
else if(val> array[middle])
{
return binarySearchWithRecursion(array, middle+1,end, val);
}
// val 在左侧
else
{
return binarySearchWithRecursion(array, start, middle-1, val);
}
}
//
递归的方式实现二分查找 , 递归需要重新构建数组,或者在参数上确定数组下标范围，所以我们使用下标来确定
public static boolean binarySearchWithRecursion(int[] array ,int start,int end ,int val)
{
//
每次递归，都把start赋值为0 这样不合理
//
start = 0;
//
end = array.length-1;
int middle = (start+end)/2;
if(val > array[end] || val < array[start])
{
searchError(val);
return false;
}
if(val == array[middle])
{
searchOk(val, middle);
return true;
}
//
val 在右侧
else if(val> array[middle])
{
return binarySearchWithRecursion(array, middle+1,end, val);
}
//
val 在左侧
else
{
return binarySearchWithRecursion(array, start, middle-1, val);
}
}测试以及解析:
[java]
public static void main(String[] args) {
int[] array = new int[]{1,3,4,5,7,10,11,12};
System.out.println("使用while的方法解析 查找存在的数字======【开始】=======");
BinarySearch.binarySearchWithWhile(array, 7);
/**
* (1)start=0,end=7,middle=(start+end)/2=3
* array[3]=5,7>5
* 所以数据在右侧,start=middle+1=3+1=4
*
* (2)start=4,end=7,middle=(start+end)/2=5
* array[5]=10,7<10,
* 所以数据在左侧,start=4,end=middle-1=5-1=4
*
* (3)start=4,end=4,middle=(start+end)/2=4
* array[4]=7,7=7
* 所以此刻我们查找到了我们的数据7,下标是middle，下标是4
*/
System.out.println("使用while的方法解析 查找不存在的数字=============");
/**
* (1)start=0,end=7,middle=(start+end)/2=3
* array[3]=5,6>5
* 所以数据在右侧,start=middle+1=3+1=4
* (2)start=4,end=7,middle=(start+end)/2=5
* array[5]=10,6<10
* 所以数据在左侧,end=middle-1=5-1=4
* (3)start=4,end=4,middle=(start+end)/2=4
* array[4]=7,6<7
* 所以数据在左侧,end=middle-1=4-1=3
* 此刻：start>end
* 所以我们判断6不存在与我们的数组中
*/
BinarySearch.binarySearchWithWhile(array, 6);
System.out.println("使用while的方法解析======【结束】=======");
/**
* for循环和while循环的机制一样
*/
BinarySearch.binatySearchWithFor(array, 6);
System.out.println("=================================");
System.out.println("=============递归=================");
System.out.println("==========查找存在的数字==============");
BinarySearch.binarySearchWithRecursion(array,0,array.length-1 ,7);
/**
* 递归方式查找解析:
*A:(1)start=0,end=7,middle=(start+end)/2=3
*array[3]=5,7>5
*E:接收到D,D来自C所以打印:恭喜 ，您要查找的数字:7已经找到,其下标为:4
* B:数据在右侧