查找算法

1.二分查找

package com.spring.test;

/**
 * Created by brady on 15-1-28.
 */
public class Bi {
    public static int f(int[] a, int l){
        int p =0;
        int left = 0;
        int right = a.length;
        while (left<=right){
            int middle = (left + right)/2;
            if(a[middle]<l) left = middle+1;
            else if(a[middle]>l) right = middle-1;
            else return middle;
        }

        return -1;
    }

    public static void main(String[] args){
        int[] a = new int[]{1,3,5,6,6,9};
        System.out.println(f(a,3));
    }
}

package com.spring.test;

/**
 * Created by brady on 15-1-28.
 */
public class Ku {

    /*
     * a为索引数组
     * b为实际数组
     * key是要查找的键值
     * length是块的长度
     *
     */
    public static int f(int[] a, int[] b, int key,int length){
        if(a.length<=0){
            return -1;
        }
        int left=0;
        int right=a.length;
        while (left<=right){
            int middle=(left+right)/2;
            if(a[middle]>key) right=middle-1;
            else if(a[middle]<=key) left=middle+1;
        }

        for(int i=left*length;i<left*length+length;i++){
            if(b[i]==key) return i;
        }
        return -1;
    }

    public static void main(String[] args){
        int[] a = new int[]{5,7,19};
        int[] b = new int[]{1,2,4,5,3,5,3,7,3,8,6,19};
        System.out.println(f(a,b,8,4));
    }

}