Binary search

演算法類型

divide and conquer, 搜尋演算法

演算法目的

利用比對 key value 來對資料進行搜尋

演算法描述

使用 binary search 的前提是資料必須是已經排序好的，接著再藉由比對資料堆中間位置的 key value 來將資料堆做二分法搜尋。舉例說明，假設有一排序好的數列如下圖:

現在假設我們要搜尋的數字是 3，就我們目前所得知的資訊，3 有可能出現在此數列的任何位置，所以目前的搜尋範圍是整個數列，我們先找出在搜尋範圍內中間位置的數字，如下圖:

我們在中間位置找到 4，很明顯的 4 不是我們要的 3，不過因為數列是已經排序好的而且 3 < 4，故我們可以確定 3 只有可能落在 4 的左邊而不可能會落在 4 的右邊，如下圖:

如此我們就可以拋棄右邊，接著繼續向左邊搜尋，所以現在的搜尋範圍變成只剩 4 的左邊，同之前的方法，直接去比對搜尋範圍中間位置的數字，如下圖:

我們在搜尋範圍中間找到 2，很明顯 2 不是我們要的 3，不過因為數列是已經排序好的而且 3 > 2，故我們可以確定 3 只有可能落在 2 的右邊而不可能會落在 2 的左邊，如下圖:

同之前的方法，我們繼續在搜尋範圍內找中間的數字做比對，以目前的情況來看，我們只剩下一個數字，如下圖:

恭喜，我們很幸運的找到 3 了，binary search 圓滿結束。如果一直二分到沒有範圍可以搜尋，則代表此數字不在數列裡。

最壞情況效率分析

設總資料量為 n, 分析單位為比較次數
binary search 的最壞情況就是要搜尋的資料不在資料堆裡，依據最壞情況可以列出以下遞迴式:

T(n) = T(n / 2) + 1
T(1) = 1

根據 master theorem，可推出此演算法效率的最壞情況為 O(lgn)

程式實作

C

#include <stdio.h>

int binarySearch(int *, int, int);

int main() {
    int arr[8] = {1, 2, 3, 4, 5, 6, 7, 8};
    int arrLength = 8;
    int findNum = 3;
    int findIndex = binarySearch(arr, arrLength, findNum);

    if (findIndex == -1)
        printf("The number %d is not in the sequence\n", findNum);
    else
        printf("The number %d is at index %d\n", findNum, findIndex);

    return 0;
}

int binarySearch(int *arr, int arrLength, int findNum) {
    int low = 0;
    int high = arrLength - 1;

    while (low <= high) {
        int mid = (low + high) / 2;

        if (findNum > arr[mid])
            low = mid + 1;
        else if (findNum == arr[mid])
            return mid;
        else
            high = mid - 1;
    }
    return -1;
}

Java

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        int findNum = 3;
        int findIndex = binarySearch(arr, findNum);

        if (findIndex == -1)
            System.out.printf("The number %d is not in the sequence\n", findNum);
        else
            System.out.printf("The number %d is at index %d\n", findNum, findIndex);
    }

    private static int binarySearch(int[] arr, int findNum) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;

            if (findNum > arr[mid])
                low = mid + 1;
            else if (findNum == arr[mid])
                return mid;
            else
                high = mid - 1;
        }
        return -1;
    }
}

Python

def binarySearch(arr, findNum):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) / 2
        if findNum > arr[mid]:
            low = mid + 1
        elif findNum == arr[mid]:
            return mid
        else:
            high = mid - 1
    return -1

arr = [1, 2, 3, 4, 5, 6, 7, 8]
findNum = 3
findIndex = binarySearch(arr, findNum)
if findIndex == -1:
    print "The number %d is not in the sequence" % (findNum)
else:
    print "The number %d is at index %d" % (findNum, findIndex)