這篇文章主要介紹了Java如何實現(xiàn)二分查找，具有一定借鑒價值，需要的朋友可以參考下。希望大家閱讀完這篇文章后大有收獲。下面讓小編帶著大家一起了解一下。

創(chuàng)新互聯(lián)主營圖們網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,app軟件開發(fā)公司,圖們h5小程序開發(fā)搭建,圖們網(wǎng)站營銷推廣歡迎圖們等地區(qū)企業(yè)咨詢

二分查找特別好理解，就類似于快排和歸并當(dāng)中用到的分治的思想，每次取中間數(shù)與目標(biāo)數(shù)相比較，然后確定是大了還是小了，區(qū)間折半。

就比如：

小紅選中了1-100中的某個數(shù)字（這個數(shù)字是56），要小明來猜，產(chǎn)生如下對話：

小明第一次猜測：68

小紅：大了

小明第二次猜測：35

小紅：小了

小明第三次猜測：58

小紅：大了

小明第四次猜測：49

小紅：小了

小明第五次猜測：54

小紅：小了

小明第六次猜測：56

小紅：bingo?。?！

我們可以看到在上面的對話中，小明每次猜測都可以縮小區(qū)間，直到回答正確

二分查找就是這樣的，比如我們現(xiàn)在有數(shù)組8，11，19，23，27，33，45，55，67，98，用二分查找如下圖：

每次都可以縮小一半的區(qū)間，我們可以看到區(qū)間變化如下：

當(dāng)區(qū)間大小無限接近1的時候k = log2n，所以時間復(fù)雜度為O(logn)。

是不是特別好理解，下面是我用Java實現(xiàn)的簡單的二分查找（備注：是最簡單的實現(xiàn)，二分查找的變體很復(fù)雜還沒掌握）

package com.structure.search;

/**
 * 二分查找法
 *
 * @author zhangxingrui
 * @create 2019-02-15 21:29
 **/
public class BinarySearch {

    public static void main(String[] args) {
        int[] nums = new int[]{4, 6, 9, 19, 30, 40, 500, 3450, 50004, 4334343};
        System.out.println(binarySearch(nums, 0, nums.length - 1, 30));
        System.out.println(binarySearch(nums, 50004));
    }

    /**
     * @Author: xingrui
     * @Description: 二分查找法（針對有序數(shù)組且不存在重復(fù)元素-遞歸方式實現(xiàn)）
     * @Date: 21:37 2019/2/15
     */
    private static int binarySearch(int[] nums, int p, int r, int k){
        if(p > r)
            return -1;

        int mid = (p + r) / 2;
        if(nums[mid] == k)
            return mid;

        if(k > nums[mid])
            return binarySearch(nums, mid + 1, r, k);
        else
            return binarySearch(nums, p,  mid - 1, k);
    }

    /**
     * @Author: xingrui
     * @Description: 二分查找法（針對有序數(shù)組且不存在重復(fù)元素-循環(huán)實現(xiàn)）
     * @Date: 21:37 2019/2/15
     */
    private static int binarySearch(int[] nums, int k){
        int p = 0;
        int r = nums.length - 1;
        while (p <= r){
            int mid = (p + r) / 2;

            if(nums[mid] == k)
                return mid;

            if(k > nums[p])
                p = mid + 1;
            else
                r = mid - 1;
        }
        return -1;
    }

}

代碼很簡單，其中需要注意的就是邊界條件p<=r。

從代碼也可以看出，簡單實現(xiàn)有很大的局限性，只能適用于有序的不存在重復(fù)數(shù)據(jù)的數(shù)組。

并且二分查找不太適合小規(guī)模的數(shù)據(jù)查詢（因為小規(guī)模的數(shù)據(jù)查詢沒有必要），這個好理解；同時呢，也不適合太大的數(shù)據(jù)的查詢，這又是為啥子呢？

就是因為上面提到的：二分查找適合底層使用數(shù)組的數(shù)據(jù)，但是數(shù)組呢又是一段連續(xù)的內(nèi)存空間，當(dāng)數(shù)據(jù)很大的時候如果要用二分查找，那么數(shù)據(jù)的底層實現(xiàn)就

只能用數(shù)組，這樣就不太好了。假設(shè)我的數(shù)據(jù)有一個G，那么我就要申請1個G的連續(xù)內(nèi)存空間，媽喲，怕吃飽球了。

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享Java如何實現(xiàn)二分查找內(nèi)容對大家有幫助，同時也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，遇到問題就找創(chuàng)新互聯(lián)，詳細(xì)的解決方法等著你來學(xué)習(xí)!