经典案例,二分查找的三种实现方式 (六)
* binarySearchWithRecursion(array,start,middle-1,val)
* 也就是:
* binarySearchWithRecursion(array,4,5-1,7)
* (1)start=4,end=(5-1)=4,middle=(start+end)/2=(4+4)/2=4
* array[4]=7,7=val(7=7)
* 所以此刻我们找到数据,返回所以true,索引为middle(middle此刻为4)
* 将数据返回到D处
*
*/
System.out.println("=================================");
System.out.println("=============递归=================");
System.out.println("==========查找不存在的数字==============");
BinarySearch.binarySearchWithRecursion(array,0,array.length-1 ,6);
/**
* A:(1)start=0,end=7,middle=(start+middle)/2=(0+7)/2=3
* array[3]=5,6>5
* 数据在右侧
* D:
* 打印出-对不起 ，您要查找的数字:6不存在
* B:(1)递归-start=middle+1=(3+1)=4
* binarySearchWithRecursion(array,start,end,val)
* 也就是
* binarySearchWithRecursion(array,3+1,7,6)
* (2)start=4,end=7,middle=(start+end)/2=(4+7)/2=5
* array[5]=10,【array[start]=7 val
* 所以,retur false
* 返回到D:
*
*/
}
}
package com.luzhiming.binarysearch;
/**
* @author fighter24h E-mail: 645707787@QQ.com
* @version 创建时间：2013-7-15 下午2:53:12
*
*/
public class BinarySearch {
private static void searchOk(int val , int index)
{
System.out.println("恭喜 ，您要查找的数字:"+val+"已经找到,其下标为:"+index);
}
private static void searchError(int val)
{
System.out.println("对不起 ，您要查找的数字:"+val+"不存在");
}
//
while方式的二分查找
public static boolean binarySearchWithWhile(int[] array , int val)
{
int start = 0 ;
int end = array.length-1;
/**
* 因为二分查找是针对有序序列的
* 所以说，我们假如序列是升序的
* 如果:val<最小的 或者大于最大的
* 我们认为，这个val不存在于我们的array中
*/
if(valarray[end])
{
searchError(val);
return false;
}
boolean flag = true;
while(flag)
{
/**
* 当我们要查找的val根本确实不存在于我们的array中的时候
* 退出二分查找的条件:start>end
*/
if(start > end)
{
searchError(val);
return false;
}
int middle = (start+end)/2;
if(val == array[middle])
{
searchOk(val, middle);
return true;
}
//
查找的元素在右侧部分
else if(val > array[middle])
{
start=middle+1;
}
//
查找的元素在左侧部分
else
{
end=middle-1;
}
}
return false;
}
//
for方式的二分查找
public static boolean binatySearchWithFor(int[] array , int val)
{
int start = 0;
int end = array.length-1;
if(valarray[end])
{
searchError(val);
return false;
}
//
其实，这种虽然使用的是for循环，但是实际上，和while的机制一样
for(;start<=end ;)
{
int middle = (start+end)/2;
//
如果查找到
if(val == array[middle])
{
searchOk(val, middle);
return true;
}
//
代表我们要查找的数字可能在左侧部分
else if(val < array[middle])
{
end = middle -1;
}
else
{
start = middle+1;
}
}
//
走到这一步代表我们没有找到我们要找的数字
searchError(val);
return false;
}
//
递归的方式实现二分查找 , 递归需要重新构建数组,或者在参数上确定数组下标范围，所以我们使用下标来确定
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;