Given an array A that has elements from the index 0 to N-1 are negative and from the index N to M-1 are positive. How do you find an algorithm that finds N in O(lg n) time complexity?

Assume the first N elements to form a binary tree. (Binary tree represented as array . Root is A[0] , for every node i , left child is A[i*2+1] and right child is A[i*2+2].)  Start at the root and proceed to the right each time, till you encounter a positive element. Let the num of levels traversed be 'L', and the current index be 'r' (r > N). Again start at the root and proceed to the left each time, for exactly 'L' levels, and let the current index be 'l'. If the value at 'l' is positive, then N=l-1. Else, perform a binary search between the indices 'l' and 'r'. Since 'L' can max be ceil(log N), so determining 'l' and 'r' takes O(log N) time. Further, 'r' - 'l' can max be N+2, so binary search will further take O(log N) time. So, overall time complexity - O(log N)..