二分查找算法（遞歸以及while）

二分查找算法

• 二分查找
• • 算法描述
  • 算法實作while 以及 遞歸 實作
  • 算法時間複雜度分析
  • 算法的應用場景
  • • 1：有序數組
    • 2：資料量适中

二分查找

在工作中，很多小夥伴應該會遇到這樣的需求，在有序的數組中查找指定元素，比如數組 nums = [1, 3, 5, 7, 8, 11, 19, 23, 27, 33, 45, 55, 67, 98] 中查找 目标資料 8，如果找到就傳回該目标資料在數組中的下标索引的位置。

算法描述

二分查找的思想也比較簡單，判斷數組中的中間元素和目标資料進行比較，如果相等，也就傳回數組中的中間元素，如果小于中間元素的話，也就說明需要查找的元素在數組中的前半部分，如果大于中間元素的話，說明在需要查找的元素在數組中的後半部分。

以上描述的是不是有點饒頭，那麼我們可以通過以下的圖示表示二分查找的整個過程。

算法實作while 以及 遞歸 實作

package com.sh.study.search;

/**
 * 二分查找,查找指定資料，并傳回目标資料在資料中的位置，-1 表示數組中沒有指定的資料
 *
 * @Author zhouwenchen
 * @Data 2020/8/13/15
 **/
public class BinarySearch {

    /**
     * 二分查找 指定目标的資料
     * 使用 while 循環實作
     *
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearch(int[] nums, int target) {
        if (nums == null) {
            return -1;
        }
        int low = 0;
        int high = nums.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = high - 1;
            }
        }
        return -1;
    }

    /**
     * 使用遞歸實作
     *
     * @param nums
     * @param target
     * @return
     */
    public static int binarySearch0(int[] nums, int start, int end, int target) {
        if (nums == null || start > end) {
            return -1;
        }
        int mid = (start + end) >> 1;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            return binarySearch0(nums, start, mid - 1, target);
        } else {
            return binarySearch0(nums, mid + 1, end, target);
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 5, 7, 8, 11, 19, 23, 27, 33, 45, 55, 67, 98};
        int target = 27;
        System.out.println("location is " + binarySearch(nums, target));
        System.out.println("location is " +  binarySearch0(nums, 0, nums.length - 1, target));
    }
}
           

算法時間複雜度分析

我們每次都可以将目标數組縮短為原數組的一半，

假設目标數組的大小是n，也就是 n ，n/2,n/4…n/2^k 求和可以得到

其中 n/2k=1 時，k 的值就是總共縮小的次數

我們可以求得 k=log2n，是以時間複雜度就是 O(logn)

算法的應用場景

1：有序數組

二分查找，主要用于有序數組中查找指定的資料。是以，二分查找需要在有序的數組中查找。

換句話，如果資料是無序的 ，或者不是以數組存儲的有序資料也是不特别适用的

2：資料量适中

如果資料量太少的情況，可以直接使用周遊就好了，沒必要使用二分查找，

如果資料量比較大的話，也不适用，因為二分查找主要底層使用數組存儲，數組需要使用一段連續的記憶體空間，如果資料量太大的話，記憶體中可能沒有那麼大的連續記憶體。基于此，那麼是否有小夥伴想着說，那我們用連結清單存儲，就不需要連續的記憶體空間了嘛？但是如果使用連結清單存儲的話，那麼每次周遊的時間複雜度就變成了O（n），相比于數組的查找資料的時間複雜度O（1）相比來說，不合适