指數搜尋(Exponential Search)演算法，搜尋目標在序列愈前面就愈快的演算法

指數搜尋(Exponential Search)演算法又稱為雙倍搜尋(Doubling Search)演算法或是蔓延搜尋(Galloping Search)演算法，是二元搜尋(Binary Search)演算法的變體。這套演算法可以在已排序好的序列中進行高效率的搜尋，要搜尋的元素在序列中愈前面的話，搜尋效能愈好。

指數搜尋法(Exponential Search)

指數搜尋法的概念

指數搜尋法是基於二元搜尋法的演算法，如果您還不了解二元搜尋法的話，請先參考這篇文章：

https://magiclen.org/binary-search/

指數搜尋法與二元搜尋法的差異在於，它在一開始的時候，並不是直接去選擇序列中間的元素來比較，而是先去比較索引值為2⁰ = 1的元素。如果發現要查找的元素比索引值為2⁰的元素還要小，表示要查找的元素不是在索引值0的位置上，要不然就是不在序列中；如果要查找的元素比索引值為2⁰的元素還要大，表示要查找的元素可能會出現在索引值為2⁰之後，此時再繼續比較要查找的元素與索引值為2^{0 + i} = 2ⁱ的元素，i為1, 2, 3, ...。如果在i迭代的過程中發現該索引值對應的元素比要查找的元素還要大時，就可以用二元搜尋法來搜尋索引值2^{i - 1} + 1 ~ 2ⁱ - 1的範圍中，是否有我們要查找的元素；如果序列是有限的，且在i迭代的過程中找不到比要查找的元素還要大的元素，則可以直接用二元搜尋法來搜尋索引值2^{i - 1} + 1 ~ 序列長度 - 1的範圍。

指數搜尋法的過程

假設現在有個已排序好的整數陣列，內容如下：

索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81

然後我們要用指數搜尋法來找到元素47。一開始先比較索引值為2⁰ = 1的元素和要查找的元素47的大小。

           ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
         47 > 9

由於查找的元素47比索引值為2⁰ = 1的元素9還要大，因此繼續與索引值為2^{i + 1} = 2^{0 + 1} = 2¹ = 2的元素做比較。

               ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
             47 > 30

由於查找的元素47比索引值為2¹ = 2的元素30還要大，因此繼續與索引值為2^{i + 1} = 2^{1 + 1} = 2² = 4的元素做比較。

                       ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                     47 > 38

由於查找的元素47比索引值為2² = 4的元素38還要大，因此繼續與索引值為2^{i + 1} = 2^{2 + 1} = 2³ = 8的元素做比較。

                                       ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                                     47 < 79

由於查找的元素47比索引值為2³ = 8的元素47還要小，因此我們可以知道如果查找的元素47要存在於該序列中的話，其索引值必定會在2² + 1 ~ 2³ - 1的範圍中，也就是5 ~ 7。接著再針對這個範圍做二元搜尋法即可。

                           ●  ○  ●
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                             47 < 61

                           ◎
索引    0   1   2   3   4   5   6   7   8   9
數值    2   9  30  32  38  47  61  69  79  81
                        47 == 47

如此一來便可以發現元素47存在序列中索引值為5的位置。若要搜尋的元素在序列中愈前面的話，就可以愈快被搜尋到。

指數搜尋法的程式實作

/// 指數搜尋法。
pub fn exponential_search(array: &[i32], target_element: i32) -> Option<usize> {
    let length = array.len();

    if length == 0 {
        None
    } else if target_element == array[0] {
        Some(0)
    } else {
        let mut two = 1;

        while two < length {
            match target_element.cmp(&array[two]) {
                Ordering::Equal => {
                    return Some(two);
                }
                Ordering::Less => {
                    return binary_search(array, target_element, (two >> 1) + 1, two - 1);
                }
                Ordering::Greater => {
                    two <<= 1;
                }
            }
        }

        binary_search(array, target_element, (two >> 1) + 1, length - 1)
    }
}

/// 二元搜尋法，使用迴圈來迭代。
pub fn binary_search(array: &[i32], target_element: i32, mut start: usize, mut end: usize) -> Option<usize> {
    while end >= start {
        let middle = start + ((end - start) >> 1);

        match target_element.cmp(&array[middle]) {
            Ordering::Equal => {
                return Some(middle);
            }
            Ordering::Greater => {
                start = middle + 1;
            }
            Ordering::Less => {
                if middle > 0 {
                    end = middle - 1;
                } else {
                    break;
                }
            }
        }
    }

    None
}

/**
 * 指數搜尋法。
 */
public static int exponentialSearch(final int[] array, final int targetElement) {
    final int length = array.length;

    if (length == 0) {
        return -1;
    }

    if (targetElement == array[0]) {
        return 0;
    }

    int two = 1;

    while (two < length) {
        if (targetElement == array[two]) {
            return two;
        } else if (targetElement < array[two]) {
            return binarySearch(array, targetElement, (two >> 1) + 1, two - 1);
        }

        two <<= 1;
    }

    return binarySearch(array, targetElement, (two >> 1) + 1, length - 1);
}

/**
 * 二元搜尋法，使用迴圈來迭代。
 */
public static int binarySearch(final int[] array, final int targetElement, int start, int end) {
    while (end >= start) {
        final int middle = (end + start) >>> 1;

        if (targetElement == array[middle]) {
            return middle;
        } else if (targetElement > array[middle]) {
            start = middle + 1;
        } else {
            end = middle - 1;
        }
    }

    return -1;
}

/**
 * 指數搜尋法。
 */
function exponentialSearch(array: number[], targetElement: number) {
    const length = array.length;

    if (length === 0) {
        return -1;
    }

    if (targetElement === array[0]) {
        return 0;
    }

    let two = 1;

    while (two < length) {
        if (targetElement === array[two]) {
            return two;
        } else if (targetElement < array[two]) {
            return binarySearch(array, targetElement, (two >> 1) + 1, two - 1);
        }

        two <<= 1;
    }

    return binarySearch(array, targetElement, (two >> 1) + 1, length - 1);
}

/**
 * 二元搜尋法，使用迴圈來迭代。
 */
function binarySearch(array: number[], targetElement: number, start: number, end: number) {
    while (end >= start) {
        const middle = start + ((end - start) >> 1);

        if (targetElement === array[middle]) {
            return middle;
        } else if (targetElement > array[middle]) {
            start = middle + 1;
        } else {
            end = middle - 1;
        }
    }

    return -1;
}

// 指數搜尋法。
func ExponentialSearch(array []int, targetElement int) int {
	length := len(array)

	if length == 0 {
		return -1
	}

	if targetElement == array[0] {
		return 0
	}

	two := 1

	for two < length {
		if targetElement == array[two] {
			return two
		} else if targetElement < array[two] {
			return BinarySearch(array, targetElement, (two>>1)+1, two-1)
		}

		two <<= 1
	}

	return BinarySearch(array, targetElement, (two>>1)+1, length-1)
}

// 二元搜尋法，使用迴圈來迭代。
func BinarySearch(array []int, targetElement int, start int, end int) int {
	for end >= start {
		middle := int(uint(end+start) >> 1)

		if targetElement == array[middle] {
			return middle
		} else if targetElement > array[middle] {
			start = middle + 1
		} else {
			end = middle - 1
		}
	}

	return -1
}

左位移一個位元等同於「乘以2」；右位移一個位元等同於「除以2」。

指數搜尋法的複雜度

以#{{n}}#來表示要搜尋的資料筆數。

項目	值	備註
最差時間複雜度	#{{O(\log n)}}#
最佳時間複雜度	#{{O(1)}}#	要查找的元素剛好位於序列的最前面。
平均時間複雜度	#{{O(\log n)}}#
最差空間複雜度(遞迴的二元搜尋法)	#{{O(\log n)}}#
最差空間複雜度(迭代的二元搜尋法)	#{{O(1)}}#