1. 二分查找算法(非遞歸) 介紹

1. 二分查找法只適用于從有序的數(shù)列中進(jìn)行查找(比如數(shù)字和字母等)，將數(shù)列排序后再進(jìn)行查找

2. 二分查找法的運(yùn)行時(shí)間為對(duì)數(shù)時(shí)間 O(㏒?n) ，即查找到需要的目標(biāo)位置最多只需要㏒?n 步，假設(shè)從[0,99]的隊(duì)列(100 個(gè)數(shù)，即 n=100)中尋到目標(biāo)數(shù) 30，則需要查找步數(shù)為㏒?100 , 即最多需要查找 7 次( 2^6 < 100 < 2^7)

2.代碼實(shí)現(xiàn)

1.需求

數(shù)組 {1,3, 8, 10, 11, 67, 100}, 編程實(shí)現(xiàn)二分查找， 要求使用非遞歸的方式完成.

public class BinarySearchNoRecur {

    public static void main(String[] args) {
        //測(cè)試
        int[] arr = {1, 3, 8, 10, 11, 67, 100};
        int index = binarySearch(arr, 100);
        System.out.println("下標(biāo): "+index);
    }

    /**
     * 二分查找的非遞歸實(shí)現(xiàn)
     * @param arr       待查找的數(shù)組,arr是升序排序
     * @param target    需要查找的數(shù)
     * @return          返回對(duì)應(yīng)下標(biāo), -1表示沒有找到
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        //說明繼續(xù)查找
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] > target) {
                // 需要向左邊查找
                right = mid - 1;
            } else {
                // 需要向右邊查找
                left = mid + 1;
            }
        }

        return -1;
    }
}