二分查找（遞歸+非遞歸）

文章目錄

• 二分查找
• 遞歸實作
• 非遞歸實作
• 附加問題：安全防溢出的兩整數平均值算法
• 相關一些題目
• • 題一：無目标值，傳回插入序号

二分查找

二分查找是一種查詢效率非常高的查找算法。又稱折半查找。

起初在資料結構中學習遞歸時實作二分查找，實際上不用遞歸也可以實作，畢竟遞歸是需要開辟額外的空間的來輔助查詢。本文就介紹兩種方法

• 優缺點

  優點是比較次數少，查找速度快，平均性能好；

其缺點是要求待查表為有序表，且插入删除困難。

是以，折半查找方法适用于不經常變動而查找頻繁的有序清單。

使用條件：查找序列是順序結構，有序。

遞歸實作

//二分查找遞歸實作
    public static int binaryserach_recursion(int arr[],int aimnum,int low,int high){
        if (aimnum<arr[low] || aimnum > arr[high] || low > high){
            return -1;
        }
        int middle=(high+low)/2;
        if (aimnum > arr[middle]){
            return binaryserach_recursion(arr,aimnum,middle+1,high);
        }else if (aimnum < arr[middle]){
            return binaryserach_recursion(arr,aimnum,low,middle-1);
        }else {
            return middle;
        }
    }
           

非遞歸實作

為何有了遞歸我們還要去看非遞歸呢？因為我們知道每當我們調用一個函數JVM會在會在虛拟機棧中建立一個棧幀，那麼當我們遞歸次數不多當然看不出來，當遞歸的次數過多，那麼我們就會撐爆虛拟機棧導緻棧溢出。

//二分查找非遞歸實作
    public static int binarySearch_loop(int arr[],int aimnum,int low,int high){
        if (aimnum<arr[low] || aimnum > arr[high] || low > high){
            return -1;
        }
        int middle=0;
        while (low <= high){
            middle=(low+high)/2;
            if (arr[middle] < aimnum){
                low = middle+1;
            }else if (arr[middle] > aimnum){
                high=middle-1;
            }
            else return middle;
        }
        return -1;
    }
           

• 注意點：

1. while (low <= high)：我們用的小于等于，而不是小于，這是保證一種情況可能少比一次，大家可以仔細思考。
2. int middle=(high+low)/2;：這裡會有可能middle是int類型可能發生溢出的風險，這個我們在下面細講。

附加問題：安全防溢出的兩整數平均值算法

我們在前面看到我們每次算兩個數的平均數數時使用的是int middle=(low+high)/2; 這個在我們int範圍内當然沒事，但是當我們資料過大會導緻溢出問題！

• 特别對于二分查找我們可以這樣修改

int right=(high-low+1)/2+low
           

• 如果對于平均，有一種專門的防溢出算法

public static int mean(int a, int b){
    return (x & y) + ((x ^ y) >> 1);
}
           

相關一些題目

題一：無目标值，傳回插入序号

• 題目描述：給定一個排序好的數組和目标值。如果在數組中找到目标值，則傳回目标值索引号。如果在數組中找不到目标值，則傳回可以插入的索引下标。

  這個題目主要是我們最後肯定會傳回一個索引，就是最後查到的索引，但是這個索引是目标值索引還是可插入索引不知道，這個時候我們可以将它抽象成一個類，兩個屬性：一個是索引值，一個是布爾值（是否是目标值）

class IndexNode{
    int index;
    Boolean flag;

    public IndexNode(int index, Boolean flag) {
        this.index = index;
        this.flag = flag;
    }
}
public class BinarySerach_withNode {


    public static IndexNode binarySerach(int arr[],int aimnum){
        IndexNode pos=new IndexNode(-1,false);
        int low=0;
        int high=arr.length-1;
        int middle=0;
        while (low <= high){
            middle=(high-low+1)/2+low;
            if (aimnum > arr[middle]){
                low=middle+1;
            }else if (aimnum < arr[middle]){
                high=middle-1;
            }else {
                pos.index=middle;
                if (arr[middle]==aimnum){
                    pos.flag=true;
                }else {
                    pos.flag=false;
                }
                break;
            }
        }
        return pos;
    }


    public static void main(String[] args) {
        int arr[]={1,2,3,4,5,67,75,88,99};
        IndexNode pos=binarySerach(arr,0);
        System.out.println(pos.index );
        System.out.println(pos.flag);
    }
}