Java查找算法

顺序查找

从第一个到最后一个纪录依次与给定值比较，若相等则查找成功

/**
 * 顺序表查找
 * 数组下标为0的位置不用来储存实际内容
 * @author Yongh
 *
 */
public class Sequential_Search {

	/*
     * 顺序查找
     */
    public int seqSearch(int[] arr,int key) {
        int n=arr.length;
        for(int i=1;i<n;i++) {  //i从1开始
            if(key==arr[i])
                return i;
        }
        return 0;
    }
    /*
     * 顺序查找优化，带哨兵
     */
    public int seqSearch2(int[] arr,int key) {
        int i=arr.length-1;
        arr[0]=key;  //将arr[0]设为哨兵
        while(arr[i]!=key)
            i--;
        return i;  //返回0说明查找失败
    }
     
    public static void main(String[] args) {
        int[] arr = {0,45,68,32,15};
        Sequential_Search aSearch = new Sequential_Search();
        System.out.println(aSearch.seqSearch(arr, 15));
        System.out.println(aSearch.seqSearch(arr, 45));

    }
}

折半查找（二分法查找）

折半查找，又称作二分查找。必须满足两个前提：
1.存储结构必须是顺序存储
2.关键码必须有序排列

public int binarySearch(int[] arr,int n,int key) {
        int low=1;
        int high=n;
        while(low<=high) {
            int mid = (low+high)/2;
            if(arr[mid]<key)
                low=mid+1;   //要+1
            else if(arr[mid]>key)
                high=mid-1;  //要-1
            else
                return mid;        
        }                      
        return 0;
    }
     
    public static void main(String[] args) {
        int[] arr = {0,1,16,24,35,47,59,62,73,88,99};
        int n=arr.length-1;
        int key=62;
        BinarySearch aSearch = new BinarySearch();
        System.out.println(aSearch.binarySearch(arr, n, key));

    }