[[396063]]

基本介紹

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

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

代碼案例

package com.xie.algorithm; 
 
public class BinarySearchNoRecur { 
    public static void main(String[] args) { 
        int[] arr = {1, 3, 8, 10, 11, 67, 100}; 
        int index = binarySearch(arr, 1); 
        System.out.println("index = " + index); 
    } 
 
    /** 
     * 二分查找非遞歸實(shí)現(xiàn) 
     * 
     * @param arr    待查找的數(shù)組,arr是升序排列 
     * @param target 需要查找的數(shù) 
     * @return 返回對應(yīng)的下標(biāo) ，-1 表示沒有找到 
     */ 
    public static int binarySearch(int[] arr, int target) { 
        int left = 0; 
        int right = arr.length - 1; 
        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; 
    } 
} 

基本介紹

1.插值查找算法類似于二分查找，不同的是插值查找每次從自適應(yīng)的mid處開始查找。

2.二分查找中求mid索引的公式轉(zhuǎn)成插值查找mid索引公式，low表示左邊的索引，high表示右邊的索引，key表示要查找的值

代碼案例

package com.xie.search; 
 
import java.util.ArrayList; 
import java.util.List; 
 
public class InsertValueSearch { 
    static int count = 0; 
 
    public static void main(String[] args) { 
        int[] arr = new int[102]; 
        arr[0] = 1; 
        arr[1] = 1; 
        for (int i = 2; i < 102; i++) { 
            arr[i] = i; 
        } 
        List<Integer> indexList = insertValueSearch(arr, 0, arr.length - 1, 1); 
        System.out.println("indexList = " + indexList); 
        System.out.println("查找次數(shù)：" + count); 
 
        /* 
        indexList = [1, 0] 
        查找次數(shù)：1 
         */ 
    } 
 
    /** 
     * 插值查找，返回索引集合 
     * 
     * @param arr       數(shù)組 
     * @param left      左邊索引 
     * @param right     右邊索引 
     * @param findValue 要查找的值 
     * @return 找到就返回所有索引的集合，沒有就返回空 
     */ 
    public static List<Integer> insertValueSearch(int[] arr, int left, int right, int findValue) { 
        count++; 
        List<Integer> indexList = new ArrayList<Integer>(); 
        //注意：findValue < arr[0] || findValue > arr[arr.length - 1] 這個必須要，否則mid可能越界 
        if (left > right || findValue < arr[0] || findValue > arr[arr.length - 1]) { 
            return new ArrayList<Integer>(); 
        } 
        int mid = left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]); 
        int midValue = arr[mid]; 
 
        if (findValue > midValue) { 
            return insertValueSearch(arr, mid + 1, right, findValue); 
        } else if (findValue < midValue) { 
            return insertValueSearch(arr, left, mid - 1, findValue); 
        } else { 
            //如果找到了，再向左掃描，將滿足條件的加入indexList 
            int temp = mid - 1; 
            while (true) { 
                if (temp < 0 || arr[temp] != findValue) { 
                    break; 
                } 
                indexList.add(temp); 
                temp--; 
            } 
 
            //再向右掃描,將滿足條件的加入indexList 
            temp = mid + 1; 
            while (true) { 
                if (temp > right || arr[temp] != findValue) { 
                    break; 
                } 
                indexList.add(temp); 
                temp++; 
            } 
            indexList.add(mid); 
            return indexList; 
        } 
    } 
} 

注意事項

1. 對于數(shù)據(jù)量大，關(guān)鍵字分布比較均勻的查找表來說，采用插值查找，速度較快。
2. 關(guān)鍵字分布不均勻的情況下，該方法不一定比二分法要好。