Reputation: 185
I am currently studying for an exam in Introduction to algorithms, and I came across a question that I can't really solve, the question is this: You have an array of n integers, the first m elements are even, and the remaining elements are odd. You need to write an algorithm that finds the value of m (finds the index of the last even number), and has time complexity of O(log m).
I thought of doing something similar to binary search and simply move left if odd and move right if even until i find the index that is even and his next one is odd, but this thing would work at O(log n) and not O(log m).
Upvotes: 4
Views: 460
Reputation: 23324
Start at index 1, then keep on doubling the index, until you find an odd entry. This gives you an upper bound for m in time O(log m). Then do binary search.
Upvotes: 5