談到搜尋不免就會探討到排序，因為Binary Search需要應用在已排序好的資料上

Linear Search

public class LinearSearch {
    public static void linearSearch(int[] numbers, int n){
        for (int i=0;i<numbers.length;i++){
            if (numbers[i]==n) {
                System.out.println("Can find "+n+" ,index is "+i);
                return;
            }

        }
        System.out.println("Can't find "+n);
    }

    public static void main(String[] args) {

        int[] numbers = {33, 99, 97, 28, 87, 72, 48, 72, 18, 89, 18, 45, 85, 13, 70, 80, 10, 88, 92, 65, 23, 73, 88, 55, 1, 79, 95,
                69, 30, 31, 88, 13, 32, 86, 15, 51, 69, 29, 11, 26, 62, 0, 45, 32, 21, 4, 73, 10, 88, 23, 93, 34, 91, 68, 8, 36, 66,
                19, 45, 12, 15, 29, 68, 59, 53, 76, 42, 81, 27, 30, 69, 15, 18, 0, 12, 2, 28, 79, 49, 15, 70, 4, 34, 48, 40, 28, 55, 73, 18, 37, 10,
                65, 95, 11, 49, 7, 22, 24, 19, 33};
        linearSearch(numbers,5);
        linearSearch(numbers,33);
    }
}

Binary Search

public class BinarySearch {
    public static void binarySearch(int[] numbers,int n){
        int min=0;
        int max=numbers.length-1;
        int step=0;
        while (min<=max){
            step++;
            int middle=(min+max)/2;
            if (n>numbers[middle]){
                min=middle+1;
            } else if (n<numbers[middle]) {
                max=middle-1;
            }else {
                System.out.println(n+" is found, its index is "+middle+" and found it spend "+step+" steps");
                return;
            }
        }
        System.out.println("Can't find "+n);
    };
    public static void main(String[] args) {
        int[] numbers = {9, 12, 15, 18, 19, 20, 22, 25, 26, 26, 33, 37, 38, 41, 47, 47, 50, 55, 57, 60,
                68, 80, 87, 90, 98, 100, 103, 108, 109, 109, 116, 120, 120, 124, 127, 128,
                131, 135, 135, 139, 143, 145, 151, 155, 156, 158, 163, 164, 165, 169, 169,
                173, 174, 176, 177, 178, 181, 182, 182, 183, 184, 189, 192, 195, 200, 201,
                203, 204, 207, 213, 217, 222, 222, 222, 227, 228, 233, 235, 237, 239, 239,
                243, 248, 251, 252, 257, 260, 260, 263, 268, 270, 271, 271, 276, 281, 284,
                285, 295, 297, 298};
        binarySearch(numbers,20);
        binarySearch(numbers,14);
        binarySearch(numbers,298);
    }
}

接著就會一堆排序方法出現，如圖：

學習到這裡有些人也不免會跟我一樣質疑

1. 為甚麼不用linear search做到底就好了
2. 為甚麼實務上很少探討Radix Sort｜Counting Sort

第一點應該可以假設：
◆ 做m次的search
則Linear Search所花時間為m*O(n)
而透過 O(nlogn)排序再使用Binary Search所花時間為 O(nlogn)+m*O(logn)
=>所以對於搜尋次數很大量時，仍會建議先排序再搜尋

第二點後來想想其實蠻直覺：
這兩種排序法都需要大量儲存空間，雖然排序時間僅要O(n)
但空間Radix需要O(r*n)空間【r個桶子n個格子】
而Counting需要O(n+k)【n個output array,k個count array】