Search in Rotated Sorted Array的升級

因為看到了這個文章 微軟面試題解析 | Search in Rotated Sorted Array .

讓我想到了前段時間才有人和我說一個30年經驗應聘高盛的人做不出這道題.

很多人都刷過這個題, 所以如果我面試我會問一個更難的題. 如果array裡面同一個數字可以出現多次呢? 可以想像, 這個array里除了一個數字是1其他都是0. 那麼就不能期望一個最壞情況下檢測這個array n次才能找到這個1的演算法. 假如任意數字在array里最多出現m次. 我想要一個 的演算法. (而且事先並不知道m是什麼)

最簡單的方法是用 找到最小值, 然後就知道rotation了, 然後利用binary search.

如何找到這個rotated sorted array的最小值? 這讓我想到我五年前寫的一個博客.

Find the minimum of a bitonic sequence?

chaoxuprime.com

推薦閱讀：