爲以下提出O（logm）算法

Question

我需要爲以下內容提出一個算法：讓我們假設我們有一個由0和1組成的數組。該數組從數組的開頭填充到索引m，所有其餘索引都填充了1。我需要在O（logm）時間找到這個索引m。這是我的想法：我認爲這就像二分搜索，首先我看看數組的中間元素，如果它是零，那麼我忘記數組的左側部分，併爲正確的部分做同樣的事情，繼續這樣，直到我遇到一個。如果中間元素是一個，那麼我忘記了正確的部分，併爲陣列的左側部分做同樣的事情。這是一個正確的O（logm）解決方案嗎？由於

Answer 1

它不是「喜歡」二進制搜索 - 它是二進制搜索。不幸的是，它是O(logN)，而不是O(logM)。

要找到O(logM)的邊界線，請從另一端開始：嘗試位置{1, 2, 4, 8, 16, ... 2^i}依此類推，直到您點擊1。然後對2^i和2^(i+1)之間的區間進行二分搜索，其中2^i+1是您發現1的第一個位置。

找到第一個1需要O(logM)，因爲索引在每次迭代中都加倍。之後，二分查找需要另一個O(logM)，因爲間隔2^i..2^(i+1)的長度也小於M。