常见查找算法（java实现）

1. 顺序查找

分析：从表中的第一个或者是最后一个记录开始，逐个的将表中记录的关键字和给定值进行比较。若某个记录的关键字和给定值相等，则查找成功；若表中所有记录的关键字和给定值都不相等，则查找失败。

java代码实现如下：

package 顺序查找;

public class OrderSearch {
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] Arr={1,23,4,56,7,89,10,123,88,6};
        System.out.println(OrderSearch(Arr,4));
        
    }
    
    public static int OrderSearch(int[] Arr,int key){
        for(int i=0;i<Arr.length;i++){
            //若查到有，则返回所对应的索引
            if(key==Arr[i]){
                return i;
            }
        }
        //没查着，返回-1
        return -1;
    }

}

2. 二分查找

分析：折半查找的前提条件是在一个有序的序列中。首先确定待查记录所在的区间，然后逐步的缩小范围区间直到找到或者找不到该记录为止。

java代码实现如下：
递归：

package 二分查找;

public class BinarySearch {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] Arr={1,2,3,4,5,6,7,8,9};
        System.out.println(binarySearch(Arr,10,0,Arr.length-1));
    }
    //递归
    public static int binarySearch(int[] Arr,int key,int low,int high){

        
        while(low<=high){
            int mid=(low+high)/2;
            if(key==Arr[mid]){
                return mid;
            }
            else if(key<Arr[mid]){
                return binarySearch(Arr,key,low,mid-1);
            }
            else{
                return binarySearch(Arr,key,mid+1,high);
            }
        }
        return -1;
    }

}

非递归：

package 二分查找;

public class BinarySearch {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] Arr={1,2,3,4,5,6,7,8,9};
        System.out.println(binarySearch(Arr,11));
    }
    
    public static int binarySearch(int[] Arr,int key){
        int low=0;
        int high=Arr.length-1;
        
        while(low<=high){
            int mid=(low+high)/2;
            if(key==Arr[mid]){
                return mid;
            }
            else if(key<Arr[mid]){
                high=mid-1; 
            }
            else{
                low=mid+1;
            }
        }
        return -1;
    }

}