查找算法 java

package com.算法.查找;

import static java.util.Arrays.sort;

public class 二分查找 {
    //二分查找要求数组有序
    //代码分别找到数据的左边界和右边界
    public static boolean flag ;
    public static void main(String[] args) {
        int[] array = new int[]{-2,0,0,1,9,8,0,-1,3,0};
        sort(array);
        int zuo = bin01(0,array);
        int you = bin02(0,array);
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
        if(flag){
            System.out.println(zuo+"  "+you); //输出左边界数据和右边界数据所在的位置
        }else{
            System.out.println("不存在此数据");
        }

    }
    public static int bin01(int data,int[] arr){ //找左边界
        int head = 0;
        int tail = arr.length;
        int mid  = (head+tail)/2;
        while(head<tail){
            if(arr[mid]==data){
                flag = true;
            }
            if(arr[mid]>=data){
                tail=mid;
            }else{
                head=mid+1;
            }
            mid  = (head+tail)/2;
        }
        return tail ;
    }
    public static int bin02(int data,int[] arr){ //找右边界
        int head = 0;
        int tail = arr.length;
        int mid = (head+tail)/2;
        while(head<tail){
            if(arr[mid]==data){
                flag = true;
            }
            if(arr[mid]<=data){
                head=mid+1;
            }else{
                tail=mid;
            }
            mid  = (head+tail)/2;
        }
        return head-1;
    }
}

package com.算法.查找;

public class 插值查找 {
    public static void main(String[] args) {
        int[] array = new int[]{0,1,2,3,5,7,8,9,11};
        int ans = cha(array,0);
        System.out.println(ans);
    }
    public static int cha(int[] arr,int data){
        int head = 0;
        int tail = arr.length-1;
        int mid = (int) (head+(data-arr[head])*(tail-head)/(0.5+arr[tail]-arr[head]));
        while(head<=tail){
            if(arr[0]>data||arr[tail]<data) return -1;
            if(arr[mid]>data){
                tail=mid-1;
            }else if(arr[mid]<data){
                head=mid+1;
            }else{
                return mid;
            }
            mid = (int) (head+(data-arr[head])*(tail-head)/(0.5+arr[tail]-arr[head]));
        }
        return head;
    }
}