查找算法总结

顺序查找

基本原理：

• 依次遍历

java代码实现：

public class SortClass {

    public static void main(String[] args){
        // 测试数据
        int[] arr = {11,2,20,0,33,13,11,66,88,66};
        int result=sequenceSearch(arr,0);
        System.out.println(result);
        
        // 运行结果：
        // 3
    }

    private static int sequenceSearch(int[] arr,int key){
        int aLength = arr.length;
        for (int i = 0; i < aLength; i++) {
            if (arr[i] == key){
                return i;
            }
        }
        return -1;
    }
}

---

折半查找

基本原理：

• 每次查找都对半分，但要求数组是有序的。

java代码实现：

public class SortClass {

    public static void main(String[] args){
        // 测试数据
        int[] arr = {0,1,2,3,4,5,6,7,8};
        int result=binarySearch(arr,6);
        System.out.println(result);

        // 运行结果：
        // 6
    }

    private static int binarySearch(int[] arr,int key){
        int low = 0;
        int aLength = arr.length-1;
       while (low<=aLength){
           int middle = (low+aLength)/2;
           if (arr[middle] == key){
               return middle;
           }else if (arr[middle]>key){
               aLength=middle-1;
           }else {
               low = middle+1;
           }
       }
        return -1;
    }
}

---