查找算法入門教程-二分查找法

關(guān)于我們常見的算法其實還有一種叫二叉堆的算法,由于涉及到二叉樹的知識學習,這里就先不說了,等到后面來講,本節(jié)我們來學習常見的查找算法-二分查找,首先來了解下什么是二分查找算法?

二分查找算法

二分查找也稱折半查找（Binary Search）绿满，它是一種效率較高的查找方法.注意:采用二分查找算法的線性表必須是有序的.接著我們通過案例來分析

案例思路分析

假設(shè)我有一組有序的線性表{1,8,10,89,1000,1234}我們輸入一個數(shù),看看該數(shù)是否存在于該線性表中,同時求出它的下標,如果沒有,就提示不存在該數(shù).

首先我們來進行思路分析

1.我們來確定該有序列表的中間下標即:int mid = (left + right) /2
2.然后讓需要查找的數(shù)findVal和中間下標所對應(yīng)數(shù)arr[mid]進行比較
2.1.如果findVal>arr[mid],則說明我們要找的數(shù)在mid的右邊,因此需要我們遞歸去找
2.2.如果findVal<arr[mid],則說明我們要找的數(shù)在mid的左邊,因此需要我們遞歸去找
2.3.如果findVal==arr[mid],則說明我們找到了,就返回mid即可

上述就是二分查找的思路分析,其實我們發(fā)現(xiàn)不難,有個問題我們需要考慮清楚,我們都知道在使用遞歸時,我們一定要知到結(jié)束遞歸的條件,這很重要,通過我們對上述案例的分析發(fā)現(xiàn)結(jié)束遞歸的條件是:

(1) .只要我們找到了就返回,這樣我們的遞歸就結(jié)束了

那么問題來了,假如沒找到了?我們結(jié)束遞歸的條件又是什么嗎?答案我們后面見揭曉,看完了思路分析我們通過代碼的方式來實現(xiàn)上述案例的查找過程

代碼實現(xiàn)

//二分查找的前提是數(shù)組必須是有序的

/**
 *
 * @param arr 要查找的數(shù)組
 * @param left 左邊下標
 * @param right 右邊下標
 * @param findVal 要查找的數(shù)
 */
public static int binarySearch(int[] arr,int left,int right,int findVal){
    //定義中間變量索引并初始化
    int mid = (left + right) /2;
    //獲取中間變量索引對應(yīng)的下標
    int midVal = arr[mid];
    //如果找不到,我們結(jié)束遞歸的條件是left > right
    if (left > right){
        return -1;
    }
    //進行查找
    if (findVal >midVal){ //表示要查找的值在右邊,我們遞歸處理
        //說明: 右邊查找我們需要改變左邊的下標也就是從 mid+1處開始去遞歸處理結(jié)果
        return binarySearch(arr,mid +1,right,findVal);
    }else if (findVal < midVal) {
        //表示要查找的值在左邊,我們遞歸處理
        //說明: 左邊查找我們需要改變右邊的下標也就是從 left - mid-1之間去遞歸處理結(jié)果
        return binarySearch(arr,left,mid -1,findVal);
    }else {
        return mid;
    }
}

不知道大家發(fā)現(xiàn)了沒.如果假如沒有找到的話,結(jié)束遞歸的條件是如下這段代碼

//如果找不到,我們結(jié)束遞歸的條件是left > right
    if (left > right){
        return -1;
    }

你想啊,在遞歸查找的過程中,如果第一次沒找到,我們left索引向前移動,right索引則需要 --操作,如果一直一直遞歸找,left > right的話,表示要找的數(shù)是不存在的,我們就需要結(jié)束遞歸了.我們來測試一把

測試代碼

''''
/**
* 查找算法-二分查找法
 */
public class BinarySearch {
public static void main(String[] args) {
    int [] arr = {1,8,10,89,1000,1234};
    int result = binarySearch(arr, 0, arr.length - 1, 55);
    System.out.println("result ="+result);

測試結(jié)果如下:

測試結(jié)果1.png

上述是在找一個不存的數(shù),我們發(fā)現(xiàn)返回-1,此時是因為我們加了結(jié)束遞歸的條件的,我們再來測一把不加添加的情況

測試結(jié)果2.png

去掉條件時,我們發(fā)現(xiàn)會報棧溢出,因為找不到遞歸結(jié)束的條件,所以在使用遞歸時特別注意這點,我們在來測試一下存在的數(shù),我們來找1000這個數(shù)

測試結(jié)果3.png

接下來我們來看下這樣一個需求:我有這樣一個有序列表 {1,8,10,89,1000,1000,1000,1234},我需要找出1000的的所對應(yīng)的下標,看完需求我們來分析下:

1.在我們找到mid下標值時,不要立即返回
2.在mid下標值的左邊進行掃描,我們將所有滿足1000元素的下標找到后存放在List中
3.在mid下標值的右邊進行掃描,我們將所有滿足1000元素的下標找到后存放在List中
4.最后返回list

最后發(fā)現(xiàn),所有的處理過程是在我們找到mid的時候進行相關(guān)的處理,我們來看代碼實現(xiàn)

代碼升級

public static List binarySearch2(int[] arr, int left, int right, int findVal){
    //定義中間變量索引并初始化
    int mid = (left + right) /2;
    //獲取中間變量索引對應(yīng)的下標
    int midVal = arr[mid];
    //如果找不到,我們結(jié)束遞歸的條件是left > right
    if (left > right){
        return new ArrayList();
    }
    //進行查找
    if (findVal >midVal){ //表示要查找的值在右邊,我們遞歸處理
        //說明: 右邊查找我們需要改變左邊的下標也就是從 mid+1處開始去遞歸處理結(jié)果
        return binarySearch2(arr,mid +1,right,findVal);
    }else if (findVal < midVal) { //表示要查找的值在左邊,我們遞歸處理
        //說明: 左邊查找我們需要改變右邊的下標也就是從 left - mid-1之間去遞歸處理結(jié)果
        return binarySearch2(arr,left,mid -1,findVal);
    }else {
        List<Integer> list = new ArrayList<>();
        //定義一個臨時的變量來存儲我們的找到的索引
        int temp = mid -1;
        //在mid下標值的左邊進行掃描,我們將所有滿足1000元素的下標找到后存放在List中
        while (true){
            if (temp <0 || arr[temp] !=findVal){ //表示極限條件,我們不需要操作,直接退出
                    break;
            }
            list.add(temp);
            temp --; //繼續(xù)找
        }
        list.add(mid); //將當前已經(jīng)找到的也存放在list中
        //在mid下標值的右邊進行掃描,我們將所有滿足1000元素的下標找到后存放在List中
        temp = mid +1; //右邊處理過程
        while (true){
            if (temp > arr.length -1 || arr[temp] !=findVal){ //右邊遍歷完了,沒有找到的話直接退出
                break;
            }
            //找到了就添加
            list.add(temp);
            temp ++; //繼續(xù)找
        }
        return list;
    }
}

測試結(jié)果如下圖:

測試結(jié)果4.png

那么關(guān)于二分查找的學習就到這里了...