二分查找：

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

創(chuàng)新互聯(lián)專(zhuān)注于松原企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站設(shè)計(jì),電子商務(wù)商城網(wǎng)站建設(shè)。松原網(wǎng)站建設(shè)公司,為松原等地區(qū)提供建站服務(wù)。全流程定制開(kāi)發(fā)，專(zhuān)業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)專(zhuā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)，如果沒(méi)有找到，就返回-1
         **/
        // 當(dāng) left > right 時(shí)，說(shuō)明遞歸整個(gè)數(shù)組，但是沒(méi)有找到
        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ù)組中滿足條件不止一個(gè)

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

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

核心代碼：

//完成一個(gè)課后思考題:
    /*
     * 課后思考題： {1,8, 10, 89, 1000, 1000，1234} 當(dāng)一個(gè)有序數(shù)組中，
     * 有多個(gè)相同的數(shù)值時(shí)，如何將所有的數(shù)值都查找到，比如這里的 1000
     *
     * 思路分析
     * 1. 在找到mid 索引值，不要馬上返回
     * 2. 向mid 索引值的左邊掃描，將所有滿足 1000， 的元素的下標(biāo)，加入到集合ArrayList
     * 3. 向mid 索引值的右邊掃描，將所有滿足 1000， 的元素的下標(biāo)，加入到集合ArrayList
     * 4. 將Arraylist返回
     */
    public static List binarySearch2(int[] arr, int left, int right, int findVal) {
        //當(dāng)left > right 時(shí),說(shuō)明遞歸整個(gè)數(shù)組，沒(méi)有找到
        if (left > right) {
            return new ArrayList();
        }
        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 resIndexlist = new ArrayList();
            //將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向左移動(dòng)
            }
            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("普通二分查找如上，升級(jí)后的二分查找如下（即能找到一個(gè)數(shù)組中滿足條件的不同下標(biāo)）");
        List resIndexList = binarySearch2(arr, 0, arr.length - 1, 1000);
        System.out.println("resIndexList=" + resIndexList);
    }

運(yùn)行結(jié)果：

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