package 查找;
import java.util.ArrayList;
public class 二分查找 {
public static void main(String[] args) {
int []a= {1,2,2,4,5,6};
ArrayList<Integer> list=erfen(a,0,a.length-1,2);
System.out.println(list);
}
static ArrayList<Integer> erfen(int []a,int left,int right,int flag) {
if(right<left)
{
System.out.println(-1);
return null;
}
int mid2=(left+right)/2;//二分查找,适用于不均匀的数
int mid=left+(right-left)*(flag-a[left])/(a[right]-a[left]);//插值查找适用于连续的数
if(a[mid]>flag) {//左递归
return erfen(a,left,mid-1,flag);
}
else if(a[mid]<flag) {//右递归
return erfen(a,mid+1,right,flag);
}
else {//找到
ArrayList<Integer> list=new ArrayList<Integer>();
int tmp=mid-1;
while(true) {
if(a[tmp]!=flag || tmp<0) {
break;
}
list.add(tmp);
tmp--;
}
list.add(mid);
int tmp2=mid+1;
while(true) {
if(a[tmp2]!=flag || tmp2>a.length-1) {
break;
}
list.add(tmp2);
tmp2++;
}
return list;
}
}
}
分享到:
最好再详细点
以后多多交流
记住这个网站了