经典案例,二分查找的三种实现方式 (四)
thRecursion(array,4,7,7)
*
(1)start=4,end=7,middle=(start+end)/2=(4+7)/2=11/2=5
*
array[5]=10,val<10(7<10)
*
D:
*
C:数据在左侧
*
递归-end=middle-1=5-1=4
*
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:
*
*/
}
首先，二分查找很重要，其次如果大家能够明白这三种凡是实现的二分查找，那么说明大家对于递归以及二分查找的原理也就认识的比较透彻了。
下面给出全部的代码，方便大家调试:
[java]
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;