CODEWITHSUNDEEP
arrayssearchbig-o
Bob
Bob

Reputation: 185

searching in an unsorted array in logrithmic time

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

Answers (1)

Henrik
Henrik

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

Related Questions