Bob*_*Bob 4 arrays big-o search
我目前正在攻读算法入门考试,我遇到了一个我无法解决的问题,问题是:你有一个n个整数的数组,前m个元素是偶数,剩下的元素很奇怪.您需要编写一个算法来查找m的值(找到最后一个偶数的索引),并且时间复杂度为O(log m).
我想做类似于二分搜索的事情,如果奇数就向左移动,如果直到我发现索引是偶数并且他的下一个是奇数,则向右移动但是这个东西在O(log n)而不是O(记录m).
Hen*_*rik 5
从索引1开始,然后继续将索引加倍,直到找到奇数条目.这为你提供了m时间O(log m)的上限.然后进行二分查找.
归档时间：
14 年，9 月 前
查看次数：
426 次
最近记录：
11 年，6 月 前