在對數時間在未排序的數組中搜索

Question

我目前正在學習算法介紹中的考試，並且遇到了一個我無法真正解決的問題，問題是：您有一個n整數數組，前m個元素是偶數，其餘元素是奇數。您需要編寫一個算法來查找m的值（查找最後偶數的索引），並且時間複雜度爲O（log m）。

我想做類似二進制搜索的東西，只需向左移動如果奇數，然後向右移動，如果直到我發現索引是偶數，而他的下一個是奇數，但這個東西在O（log n）而不是O（log m）。

Answer 1

從索引1開始，然後繼續加倍索引，直到找到奇數條目。這給你一個時間上限m（log m）。然後進行二分搜索。