Java如何實現二分查找

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

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

就比如：

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

小明第一次猜測：68

小紅：大了

小明第二次猜測：35

小紅：小了

小明第三次猜測：58

小紅：大了

小明第四次猜測：49

小紅：小了

小明第五次猜測：54

小紅：小了

小明第六次猜測：56

小紅：bingo?。?！

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

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

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

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

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

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: 二分查找法（針對有序數組且不存在重復元素-遞歸方式實現）
     * @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: 二分查找法（針對有序數組且不存在重復元素-循環實現）
     * @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。

從代碼也可以看出，簡單實現有很大的局限性，只能適用于有序的不存在重復數據的數組。

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

就是因為上面提到的：二分查找適合底層使用數組的數據，但是數組呢又是一段連續的內存空間，當數據很大的時候如果要用二分查找，那么數據的底層實現就

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

感謝你能夠認真閱讀完這篇文章，希望小編分享Java如何實現二分查找內容對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，遇到問題就找億速云，詳細的解決方法等著你來學習!