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實作二分查找的基本方法（附程式碼）的詳細內容。更多資訊請關注PHP中文網其他相關文章！