二分查找：

請對一個有序數(shù)組進行二分查找 {1,8, 10, 89, 1000, 1234} ，輸入一個數(shù)看看該數(shù)組是否存在此數(shù)，并且求出下 標(biāo)，如果沒有就提示"沒有這個數(shù)"。

創(chuàng)新互聯(lián)專注于松原企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站設(shè)計,電子商務(wù)商城網(wǎng)站建設(shè)。松原網(wǎng)站建設(shè)公司,為松原等地區(qū)提供建站服務(wù)。全流程定制開發(fā)，專業(yè)設(shè)計，全程項目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務(wù)

二分查找思路

二分查找核心代碼

 public static int binarySearch(int[] arr, int left, int right, int findVal) {
        /**
         * @description:二分查找算法
         * @author: ma lin yan
         * @date: 2022/11/6 20:45
         * @param: [arr->數(shù)組, left-->左邊的索引, right-->右邊的索引,
         * findVal-->要查找的值]
         * @return: int  如果找到就返回下標(biāo)，如果沒有找到，就返回-1
         **/
        // 當(dāng) left > right 時，說明遞歸整個數(shù)組，但是沒有找到
        if (left > right) {
            return -1;
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if (midVal < findVal) {//向右遞歸
            return binarySearch(arr, mid + 1, right, findVal);
        } else if (midVal > findVal) {
            //向左遞歸
            return binarySearch(arr, left, mid - 1, findVal);
        } else {
            return mid;
        }
    }

數(shù)組中滿足條件不止一個

說明：增加了找到所有的滿足條件的元素下標(biāo):

課后思考題： {1,8, 10, 89, 1000, 1000，1234} 當(dāng)一個有序數(shù)組中，有多個相同的數(shù)值時，如何將所有的數(shù)值 都查找到，比如這里的 1000.

核心代碼：

//完成一個課后思考題:
    /*
     * 課后思考題： {1,8, 10, 89, 1000, 1000，1234} 當(dāng)一個有序數(shù)組中，
     * 有多個相同的數(shù)值時，如何將所有的數(shù)值都查找到，比如這里的 1000
     *
     * 思路分析
     * 1. 在找到mid 索引值，不要馬上返回
     * 2. 向mid 索引值的左邊掃描，將所有滿足 1000， 的元素的下標(biāo)，加入到集合ArrayList
     * 3. 向mid 索引值的右邊掃描，將所有滿足 1000， 的元素的下標(biāo)，加入到集合ArrayList
     * 4. 將Arraylist返回
     */
    public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal) {
        //當(dāng)left > right 時,說明遞歸整個數(shù)組，沒有找到
        if (left > right) {
            return new ArrayList<Integer>();
        }
        int mid = (left + right) / 2;
        int midVal = arr[mid];

        if (midVal < findVal) {
            //向右遞歸
            return binarySearch2(arr, mid + 1, right, findVal);
        } else if (midVal > findVal) {
            //向左遞歸
            return binarySearch2(arr, left, mid - 1, findVal);
        } else {
            // * 思路分析
//			 * 1. 在找到mid 索引值，不要馬上返回
//			 * 2. 向mid 索引值的左邊掃描，將所有滿足 1000， 的元素的下標(biāo)，加入到集合ArrayList
//			 * 3. 向mid 索引值的右邊掃描，將所有滿足 1000， 的元素的下標(biāo)，加入到集合ArrayList
//			 * 4. 將Arraylist返回
            List<Integer> resIndexlist = new ArrayList<Integer>();
            //將mid索引值左邊掃描，將滿足1000的元素下標(biāo)，加入到集合ArrayList
            int temp = mid - 1;
            while (true) {
                if (temp < 0 || arr[temp] != findVal) {
                    //退出
                    break;
                }
                //否則，把temp放入到ArrayList
                resIndexlist.add(temp);
                temp = -1;//temp向左移動
            }
            resIndexlist.add(mid);//
            //將mid索引值右邊掃描，將滿足1000的元素下標(biāo)，加入到集合ArrayList
            temp = mid + 1;
            while (true) {
                if (temp > arr.length - 1 || arr[temp] != findVal) {
                    //退出
                    break;
                }
                //否則，就temp 放入到resIndexlist
                resIndexlist.add(temp);
                temp += 1;//右移
            }
            return resIndexlist;
        }
    }
}

主程序：

 public static void main(String[] args) {
        int arr[] = {1, 8, 10, 89, 1000, 1000, 1234};
        //
		int resIndex = binarySearch(arr, 0, arr.length - 1, 1000);
		System.out.println("resIndex=" + resIndex);
        System.out.println("普通二分查找如上，升級后的二分查找如下（即能找到一個數(shù)組中滿足條件的不同下標(biāo)）");
        List<Integer> resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);
        System.out.println("resIndexList=" + resIndexList);
    }

運行結(jié)果：

這篇博客是我在B站看韓順平老師數(shù)據(jù)結(jié)構(gòu)和算法的課時的筆記，記錄一下，防止忘記，也希望能幫助各位朋友。

新聞名稱：二分查找
瀏覽路徑：http://chinadenli.net/article44/dsoiohe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計、手機網(wǎng)站建設(shè)、小程序開發(fā)、軟件開發(fā)、面包屑導(dǎo)航、商城網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)