指數搜尋

習題預習

1. Exponential Search有哪些優點和缺點？

2. 如何在一個已排序的數組中使用Exponential Search來查找具有給定值的元素？

3. Exponential Search的時間複雜度是多少？與其他搜尋算法相比如何？

4. 如果在Exponential Search中找不到元素，會發生什麼？如何處理這種情況？

5. 在Python中如何實現Exponential Search？請給出代碼示例。

說明知識

指數搜索（Exponential Search）是一種用於在有序數組中查找元素的算法。相較於其他常規查找算法（如線性查找、二分查找等），它能夠更快地找到元素所在的位置。該算法通過不斷增加步長的方式，逐漸逼近目標值所在的區間。最終，再在該區間使用二分查找算法定位到目標值。

舉個例子，我們想在以下有序數組中查找元素7：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

首先，我們選擇一個步長（例如2），並將其指針i初始化為0。同時，我們也需要記錄當前步長的終止位置j，以防數組越界。因此，我們得到以下代碼：

i = 0
j = min(1, len(arr)-1)
while arr[j] < x:
i = j
j = min(j*2, len(arr)-1)

在上述代碼中，min()函數用於控制j的最大值。因為j*2的值可能會超出數組長度，因此我們需要取min()函數後的值。

接著，我們在步長所在的區間[i,j]中使用二分查找法。最終，我們可以找到元素7所在的位置（也就是在數組中的索引6）。

Exponential Search算法的時間複雜度為O(log n)，其中n表示數組中元素的數量。它的空間複雜度為O(1)。而它的優勢在於，它能夠更快地定位到目標區間，減少了二分查找法所需要的次數。

彙總重點

1. Exponential Search是一種基於二分法的搜索算法，主要用於在已排序的數組中查找元素。

2. 該算法通過一系列指數遞增的步長搜索數組，直到找到元素或者到達數組的末尾。

3. 由於Exponential Search的步長遞增速度非常快，因此可以在最壞情況下在O(logn)的時間複雜度內完成搜索。

4. 該算法的主要思想是利用二分法對數組進行區間切分，從而達到快速搜索的效果。

5. Exponential Search還具有一些優點，例如在數組中有重複元素的情況下，可以比其他搜索算法更快的找到目標元素。

6. 但是，該算法也有一些限制，例如對於非排序數組，該算法的效率並不高。

7. 此外，Exponential Search還需要額外的空間來緩存步長，這會導致一些額外的空間消耗。

知識測驗

1. 已知一個排序的整數陣列，使用指數搜尋演算法找到目標值的位置。請問當目標值不存在於陣列中時，指數搜尋最多需要幾次比較？

答案：假設陣列大小為n，指數搜尋最多需要比較2^(k-1)次，其中k為最小的正整數，使得2^k > n。

2. 已知一個遞增的有序陣列arr和一個目標值x，使用指數搜尋找到目標值x的位置。請問當陣列大小為n時，最多需要幾次比較？

答案：最多需要log2(n)次比較。

3. 已知一個有序的整數陣列，使用指數搜尋找到最後一個小於等於目標值的元素的位置。請問最多需要幾次比較？

答案：最多需要log2(n)次比較，其中n為陣列大小。

4. 已知一個有序的整數陣列，使用指數搜尋找到第一個大於等於目標值的元素的位置。請問最多需要幾次比較？

答案：最多需要log2(n)次比較，其中n為陣列大小。

5. 已知一個旋轉後的有序整數陣列，使用指數搜尋找到目標值的位置。請問當陣列大小為n時，最多需要幾次比較？

答案：最多需要log2(n)次比較。