在二維數組上進行二進制搜索以找到一個局部最大值？這個算法有什麼問題？

Question

這是一個典型的發現矩陣中的局部最大值（只有一個）。

我的算法是：

• 選擇在矩陣中心的數量。
• 檢查數字是否爲峯值。如果是，返回。

• 如果不是，請檢查左側和右側的數字。如果其中一個比我們當前的數字大，選擇矩陣的一半。如果兩者都較大​​，我們可以選擇一半。

• 用數字重複上下。這將使我們有矩陣的一個象限繼續檢查。

由於這是對於具有anxn矩陣二進制搜索N^2層的元件，它應該採取O（的log（n^2））= O（2 *的log（n））= O（的log（n ））

我很確定這是不正確的，但我的錯誤在哪裏？

Answer 1

該算法不能保證找到局部最大值。例如，考慮你需要沿着通過遞增值矩陣的蜿蜒路徑達到峯值的情況。如果該路徑在象限之間來回交叉，則算法不會找到它。

13 1 1 1 1 
12 1 1 1 1 
11 1 1 2 3 
10 1 1 1 4 
9 8 7 6 5 

或者，這裏有一個簡單的例子：

3 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 

你在中間開始，你如何找到了 '3'？你的算法沒有描述面對水平面時該怎麼做。

Answer 2

考慮閱讀Find a peak element in a 2D array，其中它描述了一個蠻力方法，以及一個有效的方法，其時間複雜度爲O(rows * log(columns))，在你的情況下爲O(nlogn)。

該算法是基於二進制搜索，從而在您的複雜性有太多的logn項：

1. 考慮中期列，並在那裏找到最大元素。
2. 設中間列索引爲'mid'，中間最大元素值爲 列爲'max'，最大元素爲'mat [max_index] [mid]'。
3. 如果max> = A [index] [mid-1] & max> = A [index] [pick + 1]，max是峯值， 返回最大值。
4. 如果最大< mat [max_index] [mid-1]，對矩陣的左半部分重複。
5. 如果最大< mat [max_index] [mid + 1]，對矩陣的右半部分重複。

---

然而，您算法不適用於所有的情況下工作，可能無法找到一個當地最大，因爲你只能看當前的中心，這並不能保證你的意志相鄰元素找到最大值（這些元素當然沒有排序）。例如：

1 1 1 1 1 
1 1 1 1 1 
1 2 1 1 1 
1 1 1 1 1 
1 1 1 1 10 

您從中心開始，你選擇了錯誤子矩陣，你註定不會找到當地最大。