package text.java;

public class searching {
    public boolean order(int[] arr,int target){
        int i=0;
        int a = target;
        while(arr[i]!=target)
        {
            i++;
            if(i==arr.length)
                break;
        }
        return i==arr.length?false:true;
    }
    public void sort(int arr[]){
        for(int i =1;i<arr.length;i++) {
            for(int j=0;j<arr.length-i;j++) {
                if(arr[j]>arr[j+1]) {
                    int temp = arr[j];

                    arr[j]=arr[j+1];

                    arr[j+1]=temp;
                }
            }
        }
    }

    public boolean binary(int[] arr,int min,int max,int mid,int target){
        boolean found = false;
        mid = (min + max) / 2;
        int midd = mid;

        if(arr[midd]==target)
            found = true;
        else if (arr[midd]!=target)
        {
            if(target<arr[midd])
            {
                max = midd-1;
                midd--;
                found = binary(arr,min,max,midd,target);
            }
            else if(target>arr[midd])
            {
                min = midd+1;
                midd++;
                found = binary(arr,min,max,midd,target);
            }
        }
        return found;
    }

    public int binaryshow(int[] arr,int min,int max,int mid,int target){
        int found = 0;
        mid = (min + max) / 2;
        int midd = mid;

        if(arr[midd]==target)
            found = arr[midd];
        else if (arr[midd]!=target)
        {
            if(target<arr[midd])
            {

                max = midd-1;
                midd--;
                found = binaryshow(arr,min,max,midd,target);
            }
            else if(target>arr[midd])
            {
                min = midd+1;
                midd++;
                found = binaryshow(arr,min,max,midd,target);
            }
        }
        return found;
    }

    public int[] hash(int[] arr){
        int[] arr1 = {0,0,0,0,0,0,0,0,0,0,0,0};
        for(int i=0;i<arr.length;i++)
        {
            if(arr1[arr[i]%11] == 0)
                arr1[arr[i]%11] = arr[i];
            else
            {
                for(int j=2;j<arr.length;j++)
                    if(arr1[j-1] == 0)
                    {
                        arr1[j-1] = arr[i];
                        break;
                    }
            }
        }
        return arr1;
    }

    public int hashsearch(int[] result,int target){
        int k = target%11,i,re = 0;
        if(result[k]==target)
            re =  result[k];
        else
        {
            for(i=k;k<result.length;k++)
            {
                if(result[k]==target)
                {
                    re = result[k];
                    break;
                }
            }
        }
        return re;
    }

    public Linked[] linkedhash(Linked[] linked){
        Linked[] arr1 = new Linked[12];
        int i;
        for(i=0;i<12;i++)
            arr1[i] = new Linked(0);
        for(i=0;i<linked.length;i++)
        {
            if((arr1[linked[i].getnum()%11]).getnum() == 0)
                arr1[linked[i].getnum()%11] = linked[i];
            else
            {
                arr1[linked[i].getnum()%11].setNext(linked[i]);
            }
        }
        return arr1;
    }

    public int linkedsearch(Linked[] re1, int target){
        int k = target%11,i,re = 0;
        if(re1[k].getnum()==target)
            re = re1[k].getnum();
        else
        {
            Linked re2 = re1[k].getNext();
            //re2 = new Linked(0);
            if(re2.getnum()==target)
                re = re2.getnum();
        }
        return re;
    }

    public static boolean FibonacciSearch(int[] table, int keyWord) {
        //确定需要的斐波那契数
        int i = 0;
        while (getFibonacci(i) - 1 == table.length) {
            i++;
        }
        //开始查找
        int low = 0;
        int height = table.length - 1;
        while (low <= height) {
            int mid = low + getFibonacci(i - 1);
            if (table[mid] == keyWord) {
                return true;
            } else if (table[mid] > keyWord) {
                height = mid - 1;
                i--;
            } else if (table[mid] < keyWord) {
                low = mid + 1;
                i -= 2;
            }
        }
        return false;
    }

    public static int getFibonacci(int n) {
        int res = 0;
        if (n == 0) {
            res = 0;
        } else if (n == 1) {
            res = 1;
        } else {
            int first = 0;
            int second = 1;
            for (int i = 2; i <= n; i++) {
                res = first + second;
                first = second;
                second = res;
            }
        }
        return res;
    }

    public static int InsertionSearch(int[] a, int value, int low, int high) {
        int mid = low + (value - a[low]) / (a[high] - a[low]) * (high - low);
        if (a[mid] == value)
            return a[mid];
        if (a[mid] > value)
            return InsertionSearch(a, value, low, mid - 1);
        else
            return InsertionSearch(a, value, mid + 1, high);
    }

    public static int blocking(int[] arr,int target){
        int[] ar1 = new int[arr.length];
        int[] ar2 = new int[arr.length];
        int[] ar3 = new int[arr.length];
        int i=0,j=0,k=0,l=0;
        int result = 0;
        for(i=0;i<arr.length;i++)
        {
            if(0<=arr[i]&&arr[i]<=20)
            {
                ar1[j] = arr[i];
                j++;
            }
            else if (20<arr[i]&&arr[i]<=60)
            {
                ar2[k] = arr[i];
                k++;
            }
            else
            {
                ar3[l] = arr[i];
                l++;
            }
        }
        i=0;
        if(0<=target&&target<=20)
        {
            for(i=0;i<ar1.length;i++)
                if(ar1[i]==target)
                {
                    result = ar1[i];
                    break;
                }
        }
        else if (20<target&&target<=60)
        {
            for(i=0;i<ar2.length;i++)
                if(ar2[i]==target)
                {
                    result = ar2[i];
                    break;
                }
        }
        else
        {
            for(i=0;i<ar3.length;i++)
                if(ar3[i]==target)
                {
                    result = ar3[i];
                    break;
                }
        }
        return result;
    }

    public String print(int[] arr){
        String result = "";
        for(int i=0;i<arr.length;i++)
            result += ""+arr[i]+" ";
        return result;
    }

}