算法--java实现查找算法

算法--java实现查找算法,第1张

1、二分查找

package use5;
public class BinarySearch {
    public static void main(String[] args) {
          int[] array = new int[]{10,11,12,13,14,15,16,17};
          int target = 10;
        int index = search(array, target);
        System.out.println(index);
    }
    public static int search(int[] array,int target){
        //最小索引指针
        int min = 0;
        int max = array.length-1;
        while (min<=max){
            //算出平均索引位置
            int mid = (min+max)/2;
            if (array[mid]== target){
                return mid;
            }
            if (array[mid]<target){
                min = mid+1;
            }
            if (array[mid]>target){
                max = mid-1;
            }
        }
        return -1;
    }
}

2、线性查找

package use5;

public class LinearSelect {

    public static void main(String[] args) {


        /**
         * 查询该数组下是否存在9这个元素,如果存在则返回索引值,否则返回-1
         */
        int[] array = new int[]{2,4,8,6,4,9,0};
        int i = show(array, 10);
        System.out.println(i);
    }
    public static int show(int[] array,int target){
        for (int i=0;i<array.length;i++){
            if (array[i]==target){
                return i;
            }
        }
        return -1;
    }
}

3、插值查找

package use5;
public class InsertSelect {
    public static void main(String[] args) {
        int[] array = {1,2,3,4,5,6};
        int left = 0;
        int right = array.length-1;
        int searchVal = 1;
        System.out.println(select(array,left,right,searchVal));
    }
    public static int select(int[] array,int left,int right,int searchVal){
        /**
         * 防止数组越界
         */
        if (left>right || searchVal<array[0] || searchVal>array[array.length-1]){
            return -1;
        }
        int mid = left+(right-left)*(searchVal-array[left])/(array[right]-array[left]);
        int midValue = array[mid];
        if (searchVal>midValue){
            return select(array,mid+1,right,searchVal);
        }else if (searchVal<midValue){
            return select(array,left,mid-1,searchVal);
        }else {
            return mid;
        }
    }
}

4、斐波那契查找

package use5;
import java.util.Arrays;
public class FibonacciSelect {
    public static void main(String[] args) {
        int[] array = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
        System.out.println(select(array,13));
    }
    /**
     * f[k] = (f[k-1])+ (f[k-2])
     * @return
     */
    public static int[] f(){
        int[] f = new int[20];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2;i<f.length;i++){
            f[i] = f[i-1]+f[i-2];
        }
        return f;
    }
    /**
     * mid = low+F(k-1)-1
     * @param array
     * @param key
     * @return
     */
    public static int select(int[] array,int key){
        int low = 0;
        int hight  = array.length-1;
        int k = 0;
        int mid = 0;
        int[] f = f();
        /**
         * 找分割点
         */
        while (hight>f[k]-1){
            k++;
        }
        int[] temp = Arrays.copyOf(array,f[k]);
        /**
         * {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89}  -=》{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,89,89,}
         */
        for (int i = hight+1;i<temp.length;i++){
            temp[i] = array[hight];
        }
        while (low<=hight){
            mid = low+f[k-1]-1;
            // f[k-1]+f[k-2] = f[k];
            if (key<temp[mid]){
                hight=mid-1;
                k--;
            }else if (key>temp[mid]){
                low = mid+1;
                k-=2;
            }else{
                if (mid<=hight){
                    return mid;
                }else {
                    return hight;
                }
            }
        }
        return -1;
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/langs/2991809.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-09-23
下一篇 2022-09-23

随机推荐

  • 含酒的诗词

    1、朱门酒肉臭,路有冻死骨。2、借问酒家何处有,牧童遥指杏花村。3、莫笑农家腊酒浑,丰年留客足鸡豚。4、金樽清酒斗十千,玉盘珍羞直万钱。5、一曲新词酒一杯,去年天气旧亭台。6、1、朱门酒肉臭,路有冻死

    2022-09-30
    0 0 0
  • 乳胶枕汗渍发黄了怎么清洗

    清洗乳胶枕汗渍必须人工手洗,并以挤压方式进行,不可放进洗衣机或其它机器设备中洗涤,否则会绞烂乳胶枕。乳胶枕在清洗时会吸附大量水分,增加重量,尽量在水中挪动,小心取出水面。洗清洗乳胶枕汗渍必须人工手洗,

    2022-09-30
    0 0 0
  • 哪些昆虫有蛹期

    蝴蝶、蛾、甲虫、苍蝇与蜂、黄蜂及蚂蚁等。蛹是指一些昆虫从幼虫变化到成虫的一种过渡形态。这个阶段只会在完全变态的昆虫出现,是在幼虫后及成虫前出现,成年昆虫的体形会在这蝴蝶、蛾、甲虫、苍蝇与蜂、黄蜂及蚂蚁

    2022-09-30
    0 0 0
  • 恐龙是胎生还是卵生

    恐龙是卵生的。在20世纪20年代,科学家们找到了恐龙的遗骨,还找到了它们留下的巢和巢里的蛋,说明恐龙是卵生的。恐龙蛋属羊膜卵,其他爬行动物以及鸡鸭等产的蛋也是羊膜卵。恐龙像恐龙是卵生的。在20世纪20

    2022-09-30
    0 0 0
  • 酵母烫死了怎么补救

    酵母烫死了可以加入酵母粉继续二次发酵,不过这一次一定要注意水温。将适量的干酵母放在温水里冲调,倒入面团里后反复搓揉,如果面团质地软可以再加面粉,面团发酵后体积会变大,就证酵母烫死了可以加入酵母粉继续二

    2022-09-30
    0 0 0
  • 公摊是什么意思

    公摊是分摊的公用建筑面积的简称。所谓公摊面积,是分摊的公用建筑面积的简称,它与套内建筑面积之和构成了一套商品房的建筑面积。如今,无论是高层还是多层,商品房都有公摊面积。公摊是分摊的公用建筑面积的简称。

    2022-09-30
    0 0 0
  • qq手机标识怎么取消

    我们用手机QQ发布说说或者聊天时,别人可以看到你是用什么机型登录的。那如果不想让被人知道的话,那qq手机标识怎么取消?qq手机标识怎么取消?1、在QQ消息界面点击左上角的在线状我们用手机QQ发布说说或

    2022-09-30
    0 0 0
  • 熨怎么读

    熨是多音字,念yùn或yù。熨读yùn时的意思是烧热后用来烫平衣服的金属器具,称“熨斗”;熨读yù时表示心情安宁、舒畅。熨的词组:熨斗(烫衣服用的金属器具)、熨平(一件刚熨好的衣服熨是多音字,念yùn

    2022-09-30
    0 0 0
  • 虎耳草科植物有哪些

    虎耳草科的植物有虎耳草、落新妇、唢呐草、山梅花、溲疏、大落新妇、扯根菜、黑茶藨子等。虎耳草又叫做石荷叶、金线吊芙蓉、老虎耳等,喜阴凉潮湿,土壤要求肥沃、湿润。落新妇虎耳草科的植物有虎耳草、落新妇、唢呐

    2022-09-30
    0 0 0

发表评论

登录后才能评论

评论列表(0条)

保存