二分搜尋法 Binary Search

基本概念:

1. 從排序後的陣列中搜尋特定元素
2. 搜尋過程由中間的元素位置開始，將要找的元素值與中間值比較
3. 假設中間值比較大則要找的元素在左半邊，start位置固定，end位置為中間位置-1
4. 假設中間值比較小則代表要找的元素在右半邊，end位置固定，start位置為中間位置+1
5. 若中間值與要找的元素值相等，則直接返回中間值位置
6. 假設搜尋過程做到start>end 還未返回要找的元素位置，則代表陣列中此元素並不存在，返回-1
7.  start>end  = 要找的元素值過大 ; end<start = 要找的元素值過小

最佳時間複雜度:  O(1)
最壞時間複雜度:  O(logn)

while寫法

    public static int bs1(int[] sortedArr,int findNum){
        int start = 0;
        int end = sortedArr.length-1;
        while(start<=end){
            int mid = (start+end)/2;
            //int mid = start + (end-start)/2; //防止int溢位
            if(findNum>sortedArr[mid])
                start = mid+1;
            else if(findNum<sortedArr[mid])
                end = mid-1;
            else
                return mid;
        }
        
        return -1;
    }

遞迴寫法

    public static int bs2(int[] sortedArr,int findNum,int start,int end){        
        if(start>end)
            return -1;
        int mid = (start+end)/2;        
        if(findNum>sortedArr[mid])
            return bs2(sortedArr,findNum,mid+1,end);
        else if(findNum<sortedArr[mid])
            return bs2(sortedArr,findNum,start,mid-1);
        else
            return mid;
    }

呼叫函式

    int sortedArr[] = {1,2,44,55,66,77,88,99};

    System.out.println(bs1(sortedArr,1));
    System.out.println(bs2(sortedArr,77,0,sortedArr.length-1));
    System.out.println(Arrays.binarySearch(sortedArr,99));