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;
 }
}
}

分享到：

赞(0) 打赏