二分查找

2020-03-04 172次浏览 已收录 7个评论
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;
 }
}
}

渣渣龙, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:二分查找
喜欢 (0)

您必须 登录 才能发表评论!

(7)个小伙伴在吐槽
  1. 最好再详细点
    渣渣辉2020-03-27 12:47
  2. 以后多多交流
    中国加油小子2020-03-27 13:38
  3. 记住这个网站了
    我是你哥2020-03-27 14:04
  4. 笨鸟先飞2020-03-28 16:27
  5. 我给你点赞了
    你哥2020-05-26 09:27
  6. 奥利给
    我是你哥2020-05-26 09:53
  7. 我给你点赞了
    小蚯蚓2020-05-26 10:44