查找算法 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;
    }
}

package com.算法.查找;

import java.util.Arrays;

public class 斐波那契查找 {
    public static void main(String[] args){
        int[] arr = new int[]{1,2,5,8,9,123,567};
        System.out.println("下标为:"+ok(123,arr));
    }
    public static int[] fib(int size){ //获取指定元数数量的斐波那契数列
        int[] f = new int[size];
        f[0]=f[2]=1;
        for(int i=2;i<size;i++){
            f[i] = f[i-1]+f[i-2];
        }
        return f;
    }
    public static int ok(int value , int[] arr){ //查找数组中指定元素的位置
           int[] fib = fib(20);
           int head = 0;
           int tail = arr.length-1;
           int k = 0;
           int mid = 0;
           while(tail>fib[k]-1){
               k++;
           }
           int[] temp = Arrays.copyOf(arr,k); //我们操作的临时数组
           int t =tail+1;
           while(temp.length>t){
                temp[t++]=arr[tail];
           }
           while(head<=tail){
              mid = head +fib[k-1]-1;
              if(temp[mid]<value){
                  head = mid +1;
                  k-=2;
              }else if(temp[mid]>value){
                  tail = mid-1;
                  k--;
              }else{
                  if(mid<=tail){
                      return mid;
                  }else{
                      return tail;
                  }
              }
           }
           return -1;
    }
}