当前位置：首页 -> AI编程基础 -> JAVA

经典案例,二分查找的三种实现方式 (一)

2014-11-24 10:16:42 · 作者: · 浏览: 0
标签: 经典案例 二分 查找 实现 方式
二分查找是建立在有序序列上的一种查找方式，所以说，前提就是被查找的序列应该是有序的。
1while方式实现的二分查找:
[java]
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;
}
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;
}
2for方式实现的二分查找:
[java]
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 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;
}
3递归方式实现的二分查找[java] view plaincopyprint
// 递归的方式实现二分查找 , 递归需要