Java使用二分法进行查找和排序的示例
实现二分法查找
二分法查找，需要数组内是一个有序的序列
二分查找比线性查找：数组的元素数越多，效率提高的越明显
二分查找的效率表示：O(log2N)N在2的M次幂范围，那查找的次数最大就是M, log2N表示2的M次幂等于N,省略常数，简写成O(logN)
如有一个200个元素的有序数组，那么二分查找的最大次数：
2^7=128,2^8=256,可以看出7次幂达不到200，8次幂包括，所以最大查找次数就等于8
//循环，二分查找
staticintbinarySearch(int[]array,intdata){
intstart=0;
intend=array.length-1;
intmid=-1;
while(start<=end){
System.out.println("查找次数");
mid=(start+end)>>>1;
if(array[mid]<data){
start=mid+1;
}elseif(array[mid]>data){
end=mid-1;
}else{
returnmid;
}
System.out.println("start="+start+",end="+end+",mid="+mid);
}
return-1;
}
//递归二分查找初始start=0,end=array.length-1
staticintbinarySearch4Recursion(int[]array,intdata,intstart,intend){
intmid=-1;
System.out.println("查找次数");
if(start>end){
returnmid;
}
mid=(start+end)>>>1;
if(array[mid]<data){
returnbinarySearch4Recursion(array,data,mid+1,end);
}elseif(array[mid]>data){
returnbinarySearch4Recursion(array,data,start,mid-1);
}else{
returnmid;
}
}
二分法插入排序
设有一个序列a[0],a[1]...a[n];其中a[i-1]前是已经有序的,当插入时a[i]时,利用二分法搜索a[i]插入的位置
效率：O(N^2)，对于初始基本有序的序列，效率上不如直接插入排序；对于随机无序的序列，效率比直接插入排序要高
/*
*二分(折半)插入排序
*设有一个序列a[0],a[1]...a[n];其中a[i-1]前是已经有序的,当插入时a[i]时,利用二分法搜索a[i]插入的位置
*/
publicclassBinaryInsertSort{
publicstaticvoidmain(String[]args){
intlen=10;
int[]ary=newint[len];
Randomrandom=newRandom();
for(intj=0;j<len;j++){
ary[j]=random.nextInt(1000);
}
binaryInsert(ary);
/*
*复杂度分析：最佳情况，即都已经排好序，则无需右移，此时时间复杂度为：O(nlgn)最差情况，全部逆序，此时复杂度为O(n^2)
*无法将最差情况的复杂度提升到O(n|logn)。
*/
//打印数组
printArray(ary);
}
/**
*插入排序
*@paramary
*/
privatestaticvoidbinaryInsert(int[]ary){
intsetValueCount=0;
//从数组第二个元素开始排序，因为第一个元素本身肯定是已经排好序的
for(intj=1;j<ary.length;j++){//复杂度n
//保存当前值
intkey=ary[j];
//∆利用二分查找定位插入位置
//intindex=binarySearchAsc(ary,ary[j],0,j-1);//复杂度：O(logn)
//intindex=binarySearchDesc(ary,ary[j],0,j-1);//复杂度：O(logn)
intindex=binarySearchDesc2(ary,ary[j],0,j-1);//复杂度：O(logn)
printArray(ary);
System.out.println("第"+j+"个索引上的元素要插入的位置是："+index);
//将目标插入位置，同时右移目标位置右边的元素
for(inti=j;i>index;i--){//复杂度,最差情况：(n-1)+(n-2)+...+n/2=O(n^2)
ary[i]=ary[i-1];//i-1<==>index
setValueCount++;
}
ary[index]=key;
setValueCount++;
}
System.out.println("\n设值次数(setValueCount)=====>"+setValueCount);
}
/**
*二分查找升序递归
*
*@paramary
*给定已排序的待查数组
*@paramtarget
*查找目标
*@paramfrom
*当前查找的范围起点
*@paramto
*当前查找的返回终点
*@return返回目标在数组中，按顺序应在的位置
*/
privatestaticintbinarySearchAsc(int[]ary,inttarget,intfrom,intto){
intrange=to-from;
//如果范围大于0，即存在两个以上的元素，则继续拆分
if(range>0){
//选定中间位
intmid=(to+from)/2;
//如果临界位不满足，则继续二分查找
if(ary[mid]>target){
/*
*mid>target,升序规则，target较小，应交换位置前置，即target定位在mid位置上，
*根据查找思想，从from到mid-1认为有序，所以to=mid-1
*/
returnbinarySearchAsc(ary,target,from,mid-1);
}else{
/*
*mid<target,升序规则，target较大，不交换位置，查找比较的起始位置应为mid+1
*/
returnbinarySearchAsc(ary,target,mid+1,to);
}
}else{
if(ary[from]>target){//如5,4,要插入的是4
returnfrom;
}else{
returnfrom+1;
}
}
}
/**
*二分查找降序，递归
*/
privatestaticintbinarySearchDesc(int[]ary,inttarget,intfrom,intto){
intrange=to-from;
if(range>0){
intmid=(from+to)>>>1;
if(ary[mid]>target){
returnbinarySearchDesc(ary,target,mid+1,to);
}else{
returnbinarySearchDesc(ary,target,from,mid-1);
}
}else{
if(ary[from]>target){//如5,4,要插入的是4
returnfrom+1;
}else{
returnfrom;
}
}
}
/**
*二分查找降序，非递归
*/
privatestaticintbinarySearchDesc2(int[]ary,inttarget,intfrom,intto){
//while(from<to){
for(;from<to;){
intmid=(from+to)>>>1;
if(ary[mid]>target){
from=mid+1;
}else{
to=mid-1;
}
}
//from<==>to;
if(ary[from]>target){//如5,4,要插入的是4
returnfrom+1;
}else{
returnfrom;
}
}
privatestaticvoidprintArray(int[]ary){
for(inti:ary){
System.out.print(i+"");
}
}
}
打印
918562442531210216931706333132第1个索引上的元素要插入的位置是：1 918562442531210216931706333132第2个索引上的元素要插入的位置是：2 918562442531210216931706333132第3个索引上的元素要插入的位置是：2 918562531442210216931706333132第4个索引上的元素要插入的位置是：4 918562531442210216931706333132第5个索引上的元素要插入的位置是：4 918562531442216210931706333132第6个索引上的元素要插入的位置是：0 931918562531442216210706333132第7个索引上的元素要插入的位置是：2 931918706562531442216210333132第8个索引上的元素要插入的位置是：6 931918706562531442333216210132第9个索引上的元素要插入的位置是：9
设值次数(setValueCount)=====>24
931918706562531442333216210132